Binary Search

Concept 

A binary search reads through a sorted list of numbers finding midpoints in order to find a particular number's position in the list. The search compares whether the desired number is equal, less than, or greater than the midpoint. If the number is equal to the midpoint, the search process is done. If the number is less than the midpoint, in the next iteration of the search, we cut off all numbers above the midpoint before calculating a new midpoint. Similarly, if the number is greater than the midpoint, we cut off all numbers less than the midpoint for the next iteration. We search until the number is equal to the midpoint and return the position of that number in the list. Otherwise, the number is not in the list.

Code

The code below is one version of binary search in Python. There are comments in the code itself, but I will draw your attention to the structure in detail. The following is a more expanded version of the Concept above:

We use a method that takes in a list and a number as inputs.

We define the original first position as position 0 and the last position as the length of the list minus 1.

We use a while loop to search through the list as long as (considering that the 'first' and 'last' positions in the list narrow down the search) first position is less than or equal to the last.

In the loop, we designate the midpoint to be between the first and last positions in the list.

If the desired number equals the midpoint, we have found the position! We return the result.

Note that .format(...) assigns variables to the bracketed words in the quotations. (This is a different way of writing a string with variables than we have seen before.)

Then, if the item in the list does not equal the midpoint, if it is less than the item in the midpoint position in the list, we change 'last' to one less than the midpoint, thereby cutting off the upper half of the list for the purpose of finding the midpoint in the next iteration of the loop.

Similarly, if the item is greater, we cut off the lower half of the list for the next iteration.

If the loop ends before returning a statement, we conclude that the item in the list is not found.

We used multiple Python features in this program that we have learned previously:

Methods

Loops

Conditionals

Variables

Arithmetic operations

:)

Sources:

I combined the following two sources in my own code for binary search

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html

https://gist.github.com/JonathanSpeek/1f4c7c283c7c3c475ee13d57381765d8