In this article, we’re going to show you how the binary search algorithm works and we’ll give you a full example code to help you perform your own binary search in Python.

What is a Binary Search algorithm

A binary search algorithm, also known as the logarithmic search or the half-interval search, is a search algorithm that looks for the position/index of an item in a sorted array. It’s called the binary search algorithm because it divides the array into two parts while searching for the position of an item. Let’s see this with the help of an example.

It’s important to note that the array or a list must be sorted in ascending order before you can use a binary search algorithm to search for items in the array.

Suppose you want to search for the integer 15 in the sorted nums list initialized in the following script.

nums = [4,9,15,21,25,28,35,38,40,45]

At the beginning, the start index will be 0. The final index will be the index of the last item in the array, 9. The middle index will be 4. The binary search algorithm uses the following formula to calculate the middle index:

start index + (end index - start index) // 2 = 4

The double forward slash in the above script specifies that only the whole number part should be returned so although 9/2 = 4.5, the middle index will be 4.

The item at the 4th index is 25. However, we are looking for the item 15 which is less than 25. Therefore the sub-list that is on the right side of the integer 25 (including the integer 25) will be chopped. And the algorithm will start looking for the item 15 in the following array:

nums = [4,9,15,21]

This illustrates the importance of why your list or array must be sorted. The binary search will again find a new middle index which will now be the index 1. The item at the index 1 is 9. Since the item that we want to search for, 15, is greater than 9, the list on the left side of the integer 9 (inclusive), will be chopped and we will be left with the following list:

nums = [15,21]

The new middle middle index in this case will be the index 2 of the original array ([4,9,15,21,25,28,35,38,40,45]). The item will again be searched at the current middle index which is 15. The item will be matched, and its index, 2, will be returned.

If the start index becomes greater than the end index but the item is not found at the middle index during each iteration, that means that the item is not present in the array.

Get Our Python Developer Kit for Free

I put together a Python Developer Kit with over 100 pre-built Python scripts covering data structures, Pandas, NumPy, Seaborn, machine learning, file processing, web scraping and a whole lot more - and I want you to have it for free. Enter your email address below and I'll send a copy your way.

Yes, I'll take a free Python Developer Kit

Implementation of the Binary Search Algorithm in Python

Here are the steps you need to perform in order to implement your own binary search algorithm in Python:

  1. Initialize three variables: start index, end index, and middle index. The start index will begin at 0, the end index will be the index of the last item in your list or array, e.g. 9 in our previous example, and the middle index will be: start index + (end index - start index) // 2.
  2. Search for the item at the middle index. If the item is found at the middle index, return its position.
  3. If the item to be searched is greater than the item at the middle index, update the start index by assigning it the value: middle index + 1.
  4. Else if the item to be searched is smaller than the item at the middle index, update the end index by assigning it the value middle index - 1.
  5. Repeat the steps 2 to 4 until the start index is less than or equal to the end index. If the start index becomes greater than the end index, the item is not found.

The following script implements the binary search algorithm in Python. The script searches for the item 15 in the nums list.

nums = [4,9,15,21,25,28,35,38,40,45]

item = 15

start_index = 0
end_index = len(nums) - 1


value_found = False

while start_index <= end_index:
    mid_index = start_index + (end_index - start_index) // 2

    item_mid_index = nums[mid_index]

    if  item == item_mid_index:
        value_found = True
        print("Item found at index ", mid_index)
        break;

    elif item > item_mid_index:
        start_index = mid_index + 1

    else: # val < val_mid_index
        end_index = mid_index - 1

if value_found == False:
    print("Item not found")

Output:

Item found at index  2

Get Our Python Developer Kit for Free

I put together a Python Developer Kit with over 100 pre-built Python scripts covering data structures, Pandas, NumPy, Seaborn, machine learning, file processing, web scraping and a whole lot more - and I want you to have it for free. Enter your email address below and I'll send a copy your way.

Yes, I'll take a free Python Developer Kit

Dry Run of our Binary Search Algorithm Code

You can dry run the above code by putting in the values for the start_index, end_index, and mid_index for each iteration. You will see that the item 15 is found at the second index during the third iteration.

nums = [4,9,15,21,25,28,35,38,40,45]

start_index = 0
end_index = 9

item = 15

Iteration 1

#mid_index = start_index + (end_index - start_index) //2
mid_index = 0 + (9 - 0 // 2) = 0 + 4 = 4
item_mid_index = nums[4] = 25

item (15) < item_mid_index (25)
end_index = mid_index - 1 = 4 - 1 = 3

Iteration 2

#mid_index = start_index + (end_index - start_index) //2
mid_index = 0 + (3 - 0 // 2) = 0 + 1 = 1
item_mid_index = nums[1] = 9

item (15) > item_mid_index (9)
start_index = mid_index + 1 = 1 - 1 = 2

Iteration 3

#mid_index = start_index + (end_index - start_index) //2
mid_index = 2 + (3 - 2 // 2) = 2 + 0 = 2
item_mid_index = nums[2] = 15

item (15) == item_mid_index (15)
return mid_index

Implementing the Binary Search Algorithm using a Function

You can implement your own binary search algorithm as a Python function, as well.

For instance, the following script implements a function named bin_search() that accepts an input array, and the item to be searched in the array. The function returns the index of the item if the item is found. Otherwise, the function returns None.

def bin_search(arr, item):

    start_index = 0
    end_index = len(arr) - 1

    while start_index <= end_index:
        mid_index = start_index + (end_index - start_index) // 2

        item_mid_index = arr[mid_index]

        if  item == item_mid_index:
            return  mid_index

        elif item > item_mid_index:
            start_index = mid_index + 1

        else: # val < val_mid_index
            end_index = mid_index - 1

    return None

The script below calls the binary_search() function to search for the position of the item 40 in the nums list.

nums = [4,9,15,21,25,28,35,38,40,45]

item = 40

index = bin_search(nums, item)
if index != None:
    print("Item found at index", index)
else:
    print("Item not found")

Output:

Item found at index 8

The binary search function can be used to find the location of non-numeric items in a sorted list, as well. Take a look at the following example:

animals = ["cat","dog","horse","jaguar","kangaroo"]

item = "jaguar"

index = bin_search(animals, item)
if index != None:
    print("Item found at index", index)
else:
    print("Item not found")

Output:

Item found at index 3

Since the binary search algorithm divides an array into two parts at each search step, the worst case complexity of the binary search is log(n). If you found this tutorial helpful and want more pre-built Python functions like this one, subscribe using the form below and we’ll send you our best (and only our best) Python guides:

Get Our Python Developer Kit for Free

I put together a Python Developer Kit with over 100 pre-built Python scripts covering data structures, Pandas, NumPy, Seaborn, machine learning, file processing, web scraping and a whole lot more - and I want you to have it for free. Enter your email address below and I'll send a copy your way.

Yes, I'll take a free Python Developer Kit