3.11 Binary Search

The most common way of traversing a list is to go through each item in order, one at a time. This is also the most basic way to search through a list. This search method is called a linear or sequential search algorithm, and it checks each value of a list in order until the result is found. 

However, this isn't the only way you can search through a list. You can also look through a list using a binary search. 

The binary search algorithm starts in the middle of a sorted data set and eliminates half of the data based on what it's looking for. It then repeats the process until the desired value is found or until the algorithm has exhausted all the values in the list.

Traversing a List

For example, let's say you had a list that looked like this:

1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12

and you wanted to find where 12 was.

If you were doing a binary search, you would divide the list in half and look at the value there, which would be 4. 

1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12

12 is greater than 4, so the program knows to disregard everything before and including that value. 

1, 1, 2, 3, 3, 4, 5, 7, 9, 11, 12

The program would then divide the list into half again...

5, 7, 9, 11, 12

and look at the value 9. 9 is less than 12, so the program would eliminate everything before and including that value.

5, 7, 9, 11, 12

This process would go on until the program either found 12 or went through all the values in the list.

Data must first be sorted in order to use a binary search method. However, when used on sorted data, a binary search is often more efficient than a sequential search because it eliminates half the data with each round of splitting. This means that it doesn't have to evaluate many of the results, saving time that the program would usually spend going down the list in a sequential sort. Due to this, the binary search method is commonly used in modern programs.

🔗 Check out this video explaining binary searches, as well as ways they can be written out. To see a binary search algorithm written in Python, go here. (Don't worry, you won't need to know how the algorithm works for the test.)