Binary search is an efficient search algorithm used to find an item in a sorted list. The algorithm works by repeatedly splitting sublists that may contain the value being searched. For large arrays, binary search is much more efficient than a linear search. Specifically, binary search runs at logarithmic time in the worst case, O(log n) while linear search runs at linear time O(n) in the worst case. In this post, we will go over how to write a binary search function in Python.
Let’s get started!
To begin, let’s define our function. We will call it ‘my_binary_search_function’:
def my_binary_search_function():
Our function will take an array called ‘input_list’ , a ‘high_value’ which corresponds to the last index, ‘low_value’ which corresponds to the first index and a ‘target_value’ which is the value we will be trying to find:
def my_binary_search_function(input_list, low_value, high_value, target_value):
Next we want to make sure our input list is in fact a list:
def my_binary_search_function(input_list, low_value, high_value, target_value):
if type(input_list)!=type([]):
print('Not a list!')
If we try to call our function with a value that is not of the type ‘list’, for example we will pass in a string, our function prints ‘Not a list!’:
my_binary_search_function('this_is_a_string', 0, 10, 2)

The next thing we need to do is check the base case. Specifically, we need to check if the ‘high_value’ is higher than the ‘low_value’. We then define the middle index of our list which will be the floor of the average of ‘high_value’ plus ‘low_value’ :
def my_binary_search_function(input_list, low_value, high_value, target_value):
...
else:
if high_value >= low_value:
middle = (high_value + low_value) // 2
If the value at the index ‘middle’ is less than the target value our function, ‘my_binary_search_function’ is called recursively with ‘low_value’ equal to ‘middle+1’:
def my_binary_search_function(input_list, low_value, high_value, target_value):
...
if input_list[middle] < target_value:
return my_binary_search_function(input_list, middle +1, high_value, target_value)
If the value at the index ‘middle’ is greater than the target value our function, ‘my_binary_search_function’ is called recursively with ‘high_value’ equal to ‘middle-1’:
def my_binary_search_function(input_list, low_value, high_value, target_value):
...
elif input_list[middle] > target_value:
return my_binary_search_function(input_list, low_value, middle-1, target_value)
Otherwise middle is returned as the index of the value we are searching for:
def my_binary_search_function(input_list, low_value, high_value, target_value):
...
else:
return middle
If the element is not in the list we return -1:
def my_binary_search_function(input_list, low_value, high_value, target_value):
...
else:
return -1
The full function is as follows:
def my_binary_search_function(input_list, low_value, high_value, target_value):
if type(input_list)!=type([]):
print('Not a list!')
else:
if high_value >= low_value:
middle = (high_value + low_value) // 2
if input_list[middle] < target_value:
return my_binary_search_function(input_list, middle +1, high_value, target_value)
elif input_list[middle] > target_value:
return my_binary_search_function(input_list, low_value, middle-1, target_value)
else:
return middle
else:
return -1
Now let’s test out our function. Let’s define a sorted list of integers:
my_list = [100, 3000, 4500, 5000, 6000, 6050, 7020, 8400, 9100]
Suppose we’d like to search for the number 6050:
my_value = 6050
We can call our function and store the returned index in a variable called ‘my_result’. If the returned index is not equal -1, we print where the value is stored. Otherwise we print that the value is not in the list:
my_result = my_binary_search_function(my_list, 0, len(my_list)-1, my_value)
if my_result != -1:
print("{} is present at index".format(my_value), str(my_result))
else:
print("{} is not present in array".format(my_value))

If we change ‘my_value’ to a number not in our list, like 80, we get the following:
my_value = 80
my_result = my_binary_search_function(my_list, 0, len(my_list)-1, my_value)
if my_result != -1:
print("{} is present at index".format(my_value), str(my_result))
else:
print("{} is not present in array".format(my_value))

I’ll stop here but feel free to play around with the code yourself.
CONCLUSIONS
To summarize, in this post we discussed how to write a binary search function in python. If you are interested in learning other important algorithms, I recommend GeeksforGeeks. I hope you found this post interesting/useful. The code from this post can be found on GitHub. Thank you for reading!