Binary Search Algorithm Explanation and Implementation in Python

What is binary search?

Binary search is an algorithm that searches an array for a specified value. You give binary search an array, and the value you want to find, and it spits out the index of that value.

Goal of binary search:

Binary Search's goal is to find the index of a given search value.

Necessary conditions for binary search:

Please note that binary search can only be performed on an ordered array.

Steps of binary search:

Find the midpoint of the array. We can determine the index of the middle value of the array by dividing the length of the array by (and rounding down to the nearest integer so our value can be used as an array index). If the midpoint happens to be the search value, our work is done - if not we continue
Check if the search value is greater or lesser than the value of the midpoint of the array. If it is greater, then we'll create a subset of the array which is everything from right above the midpoint and higher in the array. Similarly, if it is less than, we'll create a subset of the array which is everything right below the midpoint and lower.
Then we inspect the center value of the subset of the array - if it's the search value, we'll return the index of that value, but if not we'll continue back to step 2.
Keep repeating until we finally find the value we are looking for.

Each time we're dividing the data in half and looking for the middle value in the halved array.

Here's my implementation of binary search in Python:

def binary_search(array, search_item): 
    lower_bound = 0
    upper_bound = len(array)-1

    while lower_bound <= upper_bound: 

        midpoint = (upper_bound + lower_bound) // 2
        midpoint_value = array[midpoint]

        if search_item == midpoint_value: 
            return midpoint
        elif search_item > midpoint_value: 
            lower_bound = midpoint + 1
        elif search_item < midpoint_value: 
            upper_bound = midpoint - 1

    return None

Code explanation:

Our function accepts an array to search and a search_item, which is the value we are looking for. def binary_search(array, search_item):
We set our lower_bound and upper_bound, which will start off at 0 and the highest index in the array.
We start a while loop, which runs until there is no more space between the lower bound and upper bound
We find the midpoint index of the array by adding together the upper bound and lower bound and dividing the result by 2, rounded down to the nearest integer: midpoint = (upper_bound + lower_bound) // 2
We get the middle value of the array by setting the index of array to midpoint: midpoint_value = array[midpoint]
We compare the midpoint value to the search item - if they are the same, we can return the result:
```
if search_item == midpoint_value: 
          return midpoint
```
Otherwise, we check if the search item is greater than or lesser than the midpoint value. If it's greater than then we want to set our lower bound to be everything above the midpoint value. If it's lesser than then we want to set our upper bound to be everything below the midpoint value.
```
elif search_item > midpoint_value: 
          lower_bound = midpoint + 1
      elif search_item < midpoint_value: 
          upper_bound = midpoint - 1
```
If the search item is not in the array at all then we'll return None.

So suppose we want to find the value 22 in the [1, 3, 4, 5, 7, 22], we'd expect to get 5 returned, since the index of 22 in this array is 5.

If we run the following code...

print(binary_search([1, 3, 4, 5, 7, 22], 22))

...that's exactly what we get

Some terms:

algorithm: steps to follow to perform a computation
array: a collection of items, each with an index
ordered array: an array where the items are listed in order

Resources:

Check out Real Python's article on Binary Search.
I learned the information in this article from Jay Wengrow's A Common Sense Guide to Data Structures and Algorithms.

Madeline's Machine Learning Log