Lesson 3.11 Binary Search

Binary Search:

repeatedly dividing a search interval in half

Binary Search Steps:

first put the numbers in order
- ascending
- descending
find the middle number first
- this is found by taking the highest index number plus the lowest index number and divide by 2
- the numbers on the right will be greater and the numbers on the left will be smaller
- this can be represented with a binary tree
  - middle number with the smaller number branched off on the left and bigger numbers branched off on the right
these lists are not always numbers
- lists can be made with strings
- ex. ["apple", "banana", "cherry", "peach", "watermelon"]
- alphabetical order
  - a-z
  - z-a

Practice:

What is the middle number in a Binary Search given the following set of numbers in order: 1, 5, 19, 44, 89
What is the middle number in a Binary Search given the following set of numbers that are not in order: 3, 87, 12, 66, 22

Hacks:

calculate the middle index and create a binary tree for each of these lists
- 12, 14, 43, 57, 79, 80, 99
- 92, 43, 74, 66, 30, 12, 1
- 7, 13, 96, 111, 33, 84, 60
Using one of the sets of numbers from the question above, what would be the second number looked at in a binary search if the number is more than the middle number?
Which of the following lists can NOT a binary search be used in order to find a targeted value?

a. ["amy", "beverly", "christian", "devin"]

b. [-1, 2, 6, 9, 19]

c. [3, 2, 8, 12, 99]

d. ["xylophone", "snowman", "snake", "doorbell", "author"]

Rubric:

0.25/0.25 - shows full understanding of binary search, completes all hacks assigned with explanation to go above and beyond, any extra hacks to show more understanding

0.23/0.25 - shows understanding of binary search and completes all hacks

0.20/0.25 - does not understand binary search and has not completed hacks