# 03 - Binary Search

1. A binary search is …

an algorithm that is undoubtedly and undeniably the best searching technique

an algorithm that takes the data and keeps dividing it in half until it finds the item it is looking for.

an algorithm that works in binary (1s and 0s) e.g. can only search for a 0 or 1

an algorithm that uses binary sequences to analyse and search for data

2. One of the key things to know about a binary search is that you cannot:

use this technique on a sorted list

use this technique on non-binary data

use this technique on numbers

use this technique on an unsorted list

3. How would you go about performing a binary search on the following list?
`Andy, Clarke, Bob, Xavier, Fred, Jonathan`

You'd start by counting the elements in the list and doubling them

You'd start by finding the mid point

Well, you'd start by realising this is not a sorted list, so a binary search cannot be implemented

You'd start by putting 'Andy' at the end of the list

4. If you had the following list, what would the formula for finding the mid point be?
```List = Andy, Bob, Ed, Gina, Jonathan

#First add the index numbers to each element in the list

0          1         2          3             4
=========================================================
Andy       Bob       Ed        Gina        Jonathan

#Second, find the mid point by using the formula:

..........................................................................................```

midpoint = n /3

midpoint = high + low / high (where low = 0 and high = 1)

midpoint = length_of_list/4

midpoint = low+high//2 (where low = 0 and high = 4)

5. In the following code for a binary search, what is the variable 'last'?
```def binary_search(item_list,item):
first = 0
last = len(item_list)-1
found = False
mid = (first + last)//2
if item_list[mid] == item :
found = True
else:
if item < item_list[mid]:
last = mid - 1
else:
first = mid + 1
return found

print(binary_search([1,2,3,5,8], 6))
print(binary_search([1,2,3,5,8], 5))```

It stores the sum of all the elements in the list - in this case 19.

None of the above apply

It stores the length of the list -1, in this case last = 4 (the highest index number)

It stores the length of the list - in this case 5

6. After the mid point has been found, what is this line of code doing? if item_list[mid] == item : found=True

If the mid point (e.g. 2) is equal to the number being searched for, keep searching

If the mid point of the list is infact the item searched for then ….set the found flag to True (item found!)

If the mid point is not equal to the item being searched for, exit the program

None of the above apply

7. If the item being searched for is not found in the mid point, what happens next?

None of the above apply

The algorithm stops and cannot proceed

All elements except one are discarded and the remaining element is usually what we want

One half of the list is discarded

8. Which part of the code checks to see which part of the list to discard?
```def binary_search(item_list,item):
first = 0
last = len(item_list)-1
found = False
mid = (first + last)//2
if item_list[mid] == item :
found = True
else:
if item < item_list[mid]:
last = mid - 1
else:
first = mid + 1
return found

print(binary_search([1,2,3,5,8], 6))
print(binary_search([1,2,3,5,8], 5))```

Line 3: last = len(item_list)-1 …this checks to see if the item is last and therefore can be discarded

Line 10 if item < item_list[mid]: …this checks if the item is located before or after the mid point

first = 0 - this checks to see if the item being searched for is now first (e.g found)

None of the above apply

9. Here is the pseudocode for another binary search. Fill in the blanks
```OUTPUT "Which customer do you want to find?"
INPUT user inputs John Smith
STORE the user's input in the customer_name variable
customer_found = False
(we need to create a flag that identifies if the customer is found)

??-------------------------------------------------------------------------------------
Find midpoint of list
IF customer_name = record at midpoint of list THEN
customer_found = True
ELSE IF customer comes before the midpoint THEN
throw away the second half of the list
ELSE
throw away the first part of the list
OUTPUT customer details```

WHILE customer_found = False:

mid point = Found

customer_found = customer_found + 1

IF mid point = customer(1)

10. A binary search is generally excellent for…..
`If you are able, watch the video to code a binary search yourself and master the technique.`

large, sorted lists

small, unsorted lists

very small, sorted lists

large, unsorted lists