Binary Search in List in Python

In this tutorial, you will learn how to implement binary search in a list using the Python programming language.

The table of content is structured as follows:

Let’s dive into it!

Example Data

At the start, we’ll need to create some data that we can use in the following examples. It is a Python list containing six strings.

string_list = ["Statistics", "Data", "Science", 
                "Python", "String", "Hello"]    # generating an example float list

Implementing Binary Search Algorithm

The aim of the binary search algorithm is to determine whether the target value exists in the list and, if it does, to find its index. The function we will implement needs two input parameters: a sorted list and a target value. If the target value is found, the function will return its index; if not, it will return -1.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
 
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Let’s break down the implementation:

• We initialize two index variables, low and high, to track the boundaries of the search space. Initially, low is set to the first index of the list (0), and high is set to the last index (len(arr) – 1).
• We enter a while loop that iterates until the low index is less than or equal to the high index. If low becomes greater than high, it means that the target value doesn’t exist in the list.
• Inside the loop, we calculate the middle index, mid, by taking the average of low and high and using integer division //.
• We compare the value at the middle element, arr[mid], with the target value.
• If they are equal, we return the middle index mid.
• If arr[mid] is less than the target, we update low to mid + 1 because the target value must be in the right half of the remaining search space.
• If arr[mid] is greater than the target, we update high to mid - 1 because the target value must be in the left half of the remaining search space.
• If the while loop finishes without finding the target, we return -1 to indicate that the target value doesn’t exist in the list.

Now that we have our binary search function, let’s test it with some examples to see how it performs!

Example 1: Finding Target Value in List

In this example, the integer 16 will be searched in the list. If the value is included, its index will be returned.

arr = [2, 5, 7, 12, 16, 23, 36, 42]
 
target = 16
 
print(binary_search(arr, target))
# 4

As you can see, the element was found in the list, and its index 4 was returned.

Example 2: Failing to Find Target Value in List

Now let’s try an instance where the target is not included in the list.

arr = [4, 8, 15, 22, 22, 29, 33]
 
target = 10
 
print(binary_search(arr, target))
# -1

This time the output was -1. This is the default index value in case the value couldn’t be found in the list.

That’s all you have to know in this iterative binary search algorithm in Python, we hope to see you in the next tutorial!

Video, Further Resources & Summary

Do you need more explanations on how to utilize binary search in lists? Then you should have a look at the following YouTube video of the Statistics Globe YouTube channel.

The YouTube video will be added soon.

Furthermore, you could have a look at some of the other tutorials on Statistics Globe:

How to Use Lists in Python
• All Python Programming Examples

Sort List of Strings in Python
Convert List of Tuples to List of Lists in Python
Find Intersection of Two Lists in Python

This post has shown how to find the index of an element in a list via binary search. In case you have further questions, you may leave a comment below.

This page was created in collaboration with Ömer Ekiz. You may have a look at Ömer’s author page to read more about his academic background and the other articles he has written for Statistics Globe.