Binary Search In Python

Overview

We explore a Binary Search in Python 3 algorithm to look at search concepts and implement a very efficient search algorithm. We also breakdown and explain the asymptotic run time and space complexities.

In Computer Science search algorithms are a very fundamental part of learning algorithms. Binary Search is valuable because of its efficiency in looking for a value in a sorted array. Our Binary Search In Python allows us to learn about the algorithm in a very easy and beginner friendly manner.

Introduction

Binary Search In Python is a searching algorithms and is known for being able to cut search space in half. Furthermore, Binary Search is one of the two primary search algorithms, the other being a linear search. A binary search has the benefit of halving the amount of elements needed to look through.

NOTE: Binary Search requires a sorted array to work.

First, we will first explain how to do a Binary Search using normal sentences and then we will code out and explain the simple program.

Binary Search In Python 3: General Explanation

First, we begin by selecting an element in the middle of a sorted array.

Next, we compare our value to the middle element. If the middle element’s value is less than our value then use the upper or numerically higher portion of the array. If the middle element’s value is greater than our value then use the lower or numerically smaller portion of the array.

Lastly, Repeat the previous steps until the value is found or no more values exist to look through.

Binary Search In Python 3: Code Example

We can approach solving this with either a recursive solution or an iterative solution. We will show and explain both.

Iterative Approach : Code

# Iterative Binary Search In Python
#
# collection: array to be search
# lower_index: index of lowest part of search section
# upper_index: index of highest part of search section
# value: value being searched for
#
# Returns index of x in arr if present, else -1 
def iterativeBinarySearch (collection, lower_index, upper_index, value): 

    target_index = -1;

    # Base Case Check
    while(upper_index >= lower_index):
  
        mid = lower_index + (upper_index - lower_index)/2
  
        # If middle element is or value return index
        if collection[int(mid)] == value: 
            return mid 
          
        # if our middle element is greater than our search value
        # look at the lower subsection
        elif collection[int(mid)] > value: 
            upper_index = mid - 1
  
        # if our middle element has not been found and not greater than our search value
        # look at the upper or subsection with bigger values
        else: 
            lower_index = mid + 1
  
    return target_index

If we run the Iterative function with the following simple program.

# Sorted array to be searched
sorted_collection = [ 1, 2, 3, 4, 10, 40, 60, 70, 100 ] 
target_value = 10

target_index = iterativeBinarySearch(sorted_collection, 0, len(sorted_collection)-1, target_value) 
  
if target_index != -1: 
    print("Target found at index % d" % target_index) 
else: 
    print("Target not found in collection")

We obtain the following output:

Target found at index  4

Iterative Approach : Code Explained

First, we must create the function definition for our iterative Binary Search.

def iterativeBinarySearch (collection, lower_index, upper_index, value): 

Next, we setup our default return value.

target_index = -1

Furthermore, we enter out while loop. The while loop will continue until our upper and lower bounds have gone past a searchable section. I.E. the Upper bounds is now below our Lower bounds and there is nothing left to search.

    # Base Case Check
    while(upper_index >= lower_index):

Next, We setup our middle element based off the lower index and the range divided by two. The range divided by two gives us how many elements up from the lowest index our middle element is. We add this value to our lower index because our lower index may not be zero or the start of the collection as we progress in the algorithm.

       mid = lower_index + (upper_index - lower_index)/2

Now that we have setup our middle element and finish the prep work we can begin the leg work in searching for the target value.

We check if our current middle element is the target value. If it is we return it.

        # If middle element is or value return index
        if collection[int(mid)] == value: 
            return mid 

Also, if the middle element is not the target value we then see if the middle element is greater than our target value. Although, if it is greater than our target value then we must search the lower portion. Lastly, if the middle element is not greater than our target value then we must search the higher portion of collection.

        # if our middle element is greater than our search value
        # look at the lower subsection
        elif collection[int(mid)] > value: 
            upper_index = mid - 1
  
        # if our middle element has not been found and not greater than our search value
        # look at the upper or subsection with bigger values
        else: 
            lower_index = mid + 1

Lastly, If our while loop finishes and hits the end of our function then we have not returned the index of the target value. If that is the case, we must return our initial default value stored within our variable.

    return target_index

The Binary Search In Python via iterative approach is a simple and effective way to implement a binary search. We will now explore the recursive method and explain it as well.

Recursive Approach : Code

# Recursive Binary Search In Python
#
# collection: array to be search
# lower_index: index of lowest part of search section
# upper_index: index of highest part of search section
# value: value being searched for
#
# Returns index of x in arr if present, else -1 
def recursiveBinarySearch (collection, lower_index, upper_index, value): 
  
    # Base Case Check
    if upper_index >= lower_index: 
  
        mid = lower_index + (upper_index - lower_index)/2
  
        # If middle element is or value return index
        if collection[int(mid)] == value: 
            return mid 
          
        # if our middle element is greater than our search value
        # look at the lower subsection
        elif collection[int(mid)] > value: 
            return recursiveBinarySearch(collection, lower_index, mid-1, value) 
  
        # if our middle element has not been found and not greater than our search value
        # look at the upper or subsection with bigger values
        else: 
            return recursiveBinarySearch(collection, mid + 1, upper_index, value) 
  
    else: 
        # If our upper and lower indexes have past eachother or match
        #  we have finished searching
        return -1

If we run the recursive function with the following simple program.

# Sorted array to be searched
sorted_collection = [ 1, 2, 3, 4, 10, 40, 60, 70, 100 ] 
target_value = 10
  
target_index = recursiveBinarySearch(sorted_collection, 0, len(sorted_collection)-1, target_value) 
  
if target_index != -1: 
    print("Target found at index % d" % target_index) 
else: 
    print("Target not found in collection")

We obtain the following output, similar to the iterative function in our previous Binary Search in Python example.

Target found at index  4

Recursive Approach : Code Explained

Firstly, following the same convention as our Binary Search In Python iterative approach we define our function.

def recursiveBinarySearch (collection, lower_index, upper_index, value): 

Next, we setup the base case condition check. The base condition will signal we have reached the end of recursion and must return some value or finish a calculation to return. In our case we have a block of code to calculate the value to return.

    # Base Case Check
    if upper_index >= lower_index: 

Similarly to our Binary Search In Python Iterative approach, we setup the middle element index and check our middle element for the target value.

        mid = lower_index + (upper_index - lower_index)/2
  
        # If middle element is or value return index
        if collection[int(mid)] == value: 
            return mid 

Contrary to the iterative approach, if we have not returned the value then we call our function again with new lower or upper index values respectively. After all, calling our function from within our function is the definition of a recursive function.

        # if our middle element is greater than our search value
        # look at the lower subsection
        elif collection[int(mid)] > value: 
            return recursiveBinarySearch(collection, lower_index, mid-1, value) 
  
        # if our middle element has not been found and not greater than our search value
        # look at the upper or subsection with bigger values
        else: 
            return recursiveBinarySearch(collection, mid + 1, upper_index, value) 

Lastly, we finish our base case by returning a -1 if the base case condition check failed and our upper bound is below our lower bound.

    else: 
        # If our upper and lower indexes have past each other or match
        #  we have finished searching
        return -1

The Binary Search In Python via recursive function is a fun and slightly over-complex way of implementing a simple search for elements. The value from this is to understand how recursion can be used to search using the binary search algorithm.

Binary Search In Python 3: Run time Analysis

Our Binary Search In Python has been implemented in both an iterative and recursive approach. Although the recursive approach has more overhead, both the iterative and recursive methods have a run time complexity of O(log n).

The O(log n) comes from the fact we are cutting the searchable area by half with every step. If we have N elements we are not searching N elements to find a value. We are cutting the values needed to be searched by half with every function call or iterative step.

Time Complexity

O(log n)

Space Complexity

The space complexity will depend entirely on the implementation. Our implementations are broken down as follows:

Iterative Approach: O(1)

The Iterative function in our Binary Search in Python example does not grow in memory as it only uses the already allocated array memory to find the value. This does not take into account the memory for the collection as it is assumed this has already been put aside to use. The function itself does not consume more than a single stack frame for itself.

Recursive Approach: O(log n)

The Recursive function in our Binary Search in Python does grow because every call to itself requires a new stack frame to be setup on the execution stack. Since our search is O(log n) we will have at most log n function calls.

Binary Search In Python 3: Conclusion

The binary search has a great advantage in terms of time and space complexity. While the time complexity for either iterative or recursive styles is the same. The iterative function is more efficient when we measure space complexity. Either way this concept and knowledge is a great addition to any Computer Scientists or Software Engineer’s algorithm arsenal.