How to Implement Binary Search – Python for ML

Binary Search is one of the basic and important algorithm you’re expected to master in Computer Science.

Binary Search compares target value in a sorted array, with the middle value. If the value is not found then depending on if the target value is greater or lesser than the middle value, other half of the array is eliminated from search. Process repeats with new ‘half’ array until target value is found.

The key idea is that, unlike linear search, where all the elements are searched in the array, Binary search divides array into half after every loop reducing number of elements to search.

The Problem

Input : [12, 25, 36, 47, 52,64,76,88,93,102,113,124,132]

target[x] = 25

Output : found in position 1

The Approach

There are two ways to write binary search function, the recursive way and non-recursive way. We’ll use non-recursive way in this post.

First, we need an array or list which is sorted. If it’s not sorted then we cannot apply binary search on it. We’ll define a function that takes array and target element as inputs.

Then we need three variables to track different indices namely, low, mid and high.

Remember that our array is sorted and hence low will always have index of first element in the array, high will have index of last element in the array and mid will have index of (low+high)//2 element of array.

In every loop we’ll have to divide the array into half. This is easy, just change the value of high or low to mid. If you change high to mid, second half of array is eliminated from search and if you change low to mid, first half of array is eliminated. How will you chose which half to eliminate ?

Before you change values of low and high, you need to search if target value is mid of the array. If not, check if target value is greater than mid. If so, first half of array is of no use and hence it can be eliminated. Change value of low to new value which is mid. Change mid to new mid.

Show me the code

arr = [12, 25, 36, 47, 52,64,76,88,93,102,113,124,132]
x= 25

### Function Starts
def binary_search_nonrecursive(arr,x):
    high = len(arr)-1
    low=0
    
    
    while(high>=low):
        
        mid = (high+low)//2
        
        if(x == arr[mid]):
            return mid
        elif(x>arr[mid]):
            low = mid+1

        else:
            high = mid-1

    
    return -1

### End of Function

found = binary_search_nonrecursive(arr,x)

if found:
    print(f"Given value is found in Position -> {found} of the array")
else:
    print("Given value not found in array")

Explanation

Let’s see what happens in each while loop inside the function after it is called –binary_search_nonrecursive(arr,x)

The above image shows values of variables at each loop.

Loop1

mid = (high+low)//2

low = 0, high = 12 mid = 6. Target value is at position 1.

The algorithm will search if target value is the mid value of array, i,e. if (25==76).

if(x == arr[mid]):
      return mid

Values are not equal and target value is less than mid value.

else:
   high = mid-1

Hence new high should be one position less than the old mid (5). low would remain same.

New mid would be (0+5)//2 = 2 . Note that this would be calculated at the beginning of next loop.

Loop 2

low = 0, high = 5 mid = 2. Target value is at position 1.

Algorithm will check if target value is same as mid value.

Values are not equal and target value is less than mid value. Hence new high should be calculated. High = mid -1 = 1. mid = (0+1)//2 = 0

Loop 3

low = 0, high = 1 mid = 0.

Values are again not matching at mid as our target value is at position 1. So new values are computed for low, mid & high.

Target value is greater than mid value. Hence we need to update low.

elif(x>arr[mid]):
     low = mid+1

low= mid+1 = (0+1) = 1

high = remains the same

mid = (1+1)//2 = 1

Loop 4

low = 1, high = 1 mid = 1.

Now algorithm will match mid value with target value. Values are matching and hence algorithm will return the position of mid which is 1.

Last part of the code which checks if variable found has any value greater than 1. If so it will print positive message.

Conclusion.

We have understood the concept behind the binary search. We then looked into the problem and importance of three variables in binary search (low,mid,high). Finally we looked into each loop tracing values of the variables.

Feel free to debug this code on your own. Change the input and see of you get the expected output. I hope you can implement binary search on your own now.