Learn about Binary Search in Python

Introduction

Binary Search is one of the popular search techniques in the data structure. This is commonly used to find the index of an element in the sorted(ascending or descending) list or array. 

You may be thinking why I called sorted lists or arrays. Because binary search algorithm does not work for unsorted array or list. In this tutorial, you'll learn about binary search in python. We'll perform this search technique here in two ways. The first one is an iterative method and the second is recursion.

How does binary search work?

We're assuming the data elements of the given array are in ascending order. If it's not then don't worry; the logic is almost the same except for some minor changes.

Step 1: Set low = 0 and high = length of the array

Step 2: Run a while loop till 'low' is less than or equal to 'high'

Step 3: Find the middle index of the array ('mid')

Step 4: If the key or search element is equal to the 'mid' of the array element, return the 'mid' index

Step 5: If the key is less than the 'mid' element, set high = mid - 1 and continue from Step 3

Step 6: If the key is greater than the 'mid' element, set low = mid + 1 and continue from Step 3

Step 7: If the loop ends and the search item is still not found, return -1 as a status. 

For descending array

Only Step 5 and Step 6 will change a bit. The rest are still the same.

Step 5: If the key is less than the 'mid' element, set low = mid + 1 and continue from Step 3

Step 6: If the key is greater than the 'mid' element, set high = mid - 1 and continue from Step 3

Binary search using the iterative method

Code

'''Binary search program in python'''
def BinarySearch(arr, key):
    low = 0
    high = len(arr)

    while low <= high:
        # finding the mid
        mid = int((low+high)//2)

        if key == arr[mid]:
            return mid
        elif key < arr[mid]:
            high = mid - 1
        elif key > arr[mid]:
            low = mid + 1
    return -1 

if __name__=="__main__":
    # Array in the ascending order
    arr = [1, 4, 5, 6, 7, 8, 12, 14, 18]
    key = int(input("Please enter the key: "))

    result = BinarySearch(arr, key)
    if result == -1:
        print("Sorry!, The key is not found!")
    else:
        print(f"The key has found at index no. {result+1}")

Output

Please enter the key: 12
The key has found at index no. 7

Binary search using recursion

Code

'''Binary search using recursion in python'''
def BinarySearch(arr, low, high ,key):
    if low <= high:
        # finding the mid
        mid = int((low+high)//2)

        if key == arr[mid]:
            return mid
        elif key < arr[mid]:
            return BinarySearch(arr, low, mid -1, key)
        elif key > arr[mid]:
            return BinarySearch(arr, mid + 1, high, key)
    return -1 

if __name__=="__main__":
    # Array in the ascending order
    arr = [1, 4, 5, 6, 7, 8, 12, 14, 18]

    low = 0
    high = len(arr)
    # Take the input from the user
    key = int(input("Please enter the key: "))
    # Calling the function
    result = BinarySearch(arr, low, high, key)
    if result == -1:
        print("Sorry!, The key is not found!")
    else:
        print(f"The key has found at index no. {result+1}")

Output

Please enter the key: 8
The key has found at index no. 6

Complexity Analysis

Time Complexity of Binary Search

Best Case: O(1) If the middle element directly matches the result item

Worst Case: O(logn)

Space Complexity of Binary Search

Space Complexity: O(1) There is no need for any extra spaces