Two ways to implement Binary Search in Python

Next to linear search, binary search is arguably the simplest to implement among the many search algorithms. Binary search can be summarized with the following rules:

  1. The list in which we are performing the search should be sorted beforehand.
  2. If the value being searched is less than the value in the middle of the list, then search only on the left side of the list.
  3. Otherwise, search only on the right side of the list.
  4. The value being searched is always in the middle.

Rules 2 and 3 give a hint as to why binary search is referred to as “divide and conquer search”. Basically, we “divide” the list into two, and “conquer” (i.e., perform the search on) one side. We keep performing this “divide-and-conquer” concept either iteratively or recursively, until we find the value we are looking for or until we’ve exhausted the search.

For example, in this list, we’re looking for the value 23.

The search would look like the following:

Method #1: Iterative Binary Search

The more common way of implementing binary search is through a loop which iterates through sections of the list.

We first define a function that accepts the list arr and the value we are searching for val. For this, we’ll assume that the values in arr are already sorted. We’ll initialize variables first and last, which are pointers to the lower bound and the upper bound of the list, respectively. We’ll be updating these variables as we search through the list.

def iterativeBinarySearch(arr, val):
  first = 0
  last = len(arr) - 1

Next, we’ll look for middle point between first and last. This can be calculated as the following (note that double slash means integer division):

mid = (first + last) // 2 

If the value in the middle matches the value we are looking for, then we can return the value of mid and that would be our answer. Otherwise, we’ll need to update value of first or last, depending on how the value we are looking for compares with the value in the middle of the search space. For example, if the value we are looking for is less than the value in the middle, then we change last with mid – 1, which will then limit our search space to only the left side of the list. If the value is more than the value in the middle, then we change the first variable with mid + 1, which will limit our search space to only the right side of the list. This logic is defined in the outer else statement of the code:

if arr[mid] == val:
  return mid

elif val < arr[mid]:
  last = mid - 1

elif val > arr[mid]:
  first = mid + 1

Now that we have implemented all of the rules of binary search in our code, we can then put them all together and use a while loop to iteratively update the first and last variables until there are no more elements to look at. We know whether there are logically no more elements to search if the value of first exceeds the value of last. Once we’ve passed that condition, then the function will return -1, meaning that the value was not found.

def iterativeBinarySearch(arr, val):
  first = 0
  last = len(arr) - 1

  while (first <= last):
    mid = (first + last) // 2

    if arr[mid] == val:
      return mid

    elif val < arr[mid]:
        last = mid - 1

    elif val > arr[mid]:
        first = mid + 1
  
  return -1

Method #2: Recursive Binary Search

Once we’ve grasped the rules of binary search, it’s quite simple to modify the iterative approach into a recursive one. We know that the terminating condition of binary search is if the value of the supposed lower bound first exceeds the value of the supposed upper bound last. So, we can already define that in our recursive function:

def recursiveBinarySearch(arr, val, first, last):
  if first > last:
    return -1

The rest of the function will then look almost the same as the iterative approach, with the only difference that we recursively call the function along with the updates to first and last when we’ve met the conditions.

if arr[mid] == val:
  return mid

elif val < arr[mid]:
  return binarySearch(arr, val, first, mid-1)

elif val > arr[mid]:
  return binarySearch(arr, val, mid+1, last)

Putting it all together, the recursive binary search would look like this:

def recursiveBinarySearch(arr, val, first, last):
  if first > last:
    return -1
  else:
    mid = (first + last) // 2

    if arr[mid] == val:
      return mid

    elif val < arr[mid]:
      return recursiveBinarySearch(arr, val, first, mid-1)

    elif val > arr[mid]:
      return recursiveBinarySearch(arr, val, mid+1, last)

For more code on different search algorithms, check out my notebook on Github.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: