# Binary Search

The binary search is used to find an item in an ORDERED list.

For example, we want to find a number in the list below:

1 | ```
2, 5, 7, 12, 14, 21, 28, 31, 36
``` |

To search for an item, look in the middle of the list and see if the number you want is in the middle, above the middle or below the middle. If it is in the middle, you have found the item. If it is higher than the middle value, then adjust the bottom of the list so that you search in a smaller list starting one above the middle of the list. If the number is lower than the middle value, then adjust the top of the list so that you search in a smaller list which has its highest position one less than the middle position.

The algorithm is as follows (given a list called 'List' and looking for an item called 'item'):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | ```
Found <- False
while not Found and first <= top
Midpoint <- (First + Last) DIV 2
If List[Midpoint] = ItemSought Then
ItemFound <- True
Else
If First >= Last Then
SearchFailed <- True
Else
If List[Midpoint] > ItemSought Then
Last <- Midpoint - 1
Else
First <- Midpoint + 1
EndIf
EndIf
EndIf
``` |

This video clip shows how to write a binary search in Python:

## Exercises

- Implement the binary search as described in the video and using the algorithm. Test that it works with items in and not in the list
- Add a counter to report how many searches have been done for each item searched for

**Previous**- Linear Search**Next**- Bubble Sort