Binary Search Algorithm in Python.

There are two popular searching algorithms to find a target value in an Array 'Linear Search' and 'Binary Search'. In this article, we will learn about the Binary Search Algorithm in detail using Python Programming.

Binary Search Algorithm.

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. The only drawback of this search algorithm is that we need a sorted array to perform our search operation to find the target element in the given list. 

Below are the algorithm steps to follow:

Step 1: Set two pointers, low and high, to the start and end of the array, respectively.

Step 2: Loop until the base case is reached:

• Calculate the middle index as (low + high) // 2.

• If the element at the middle index is equal to the target, return the index.

• If the element is greater than the target, update high to mid - 1 and repeat the search in the left half.

• If the element is smaller than the target, update low to mid + 1 and repeat the search in the right half.

Step 3: If low is greater than high, the target is not present. Return -1.

Example of Binary Search:

Let's go through an example to understand the workings of the Binary Search Algorithm.

We have a sorted array [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], and we want to find the index of element 13.

Initialize Pointers: Set low to 0 and high to 9 (the indices of the array's first and last elements).

Iteration 1:

• Calculate mid as (low + high) // 2 = (0 + 9) // 2 = 4.
• Compare arr[mid] (element at index 4) with the target (13).
• Since arr[4] is less than 13, update low to mid + 1, making low = 5.

Iteration 2:

• Calculate mid as (low + high) // 2 = (5 + 9) // 2 = 7.
• Compare arr[mid] (element at index 7) with the target (13).
• Since arr[7] is greater than 13, update high to mid-1, making high = 6.

Iteration 3:

• Calculate mid as (low + high) // 2 = (5+ 6) // 2 = 5.
• Compare arr[mid] (element at index 5) with the target (13).
• Since arr[5] is less than 13, update low to mid + 1, making low = 6.

Iteration 4:

• Calculate mid as (low + high) // 2 = (6 + 6) // 2 = 6.
• Compare arr[mid] (element at index 6) with the target (13).
• Since arr[6] is equal to 13, we found the target. Return the index 6.

The target element 13 is present at index 9 in the array.

Python Program for Binary Search Using Iteration.

# Python code for Iterative Binary Search to find
# target element from sorted array
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        mid_element = arr[mid]

        if mid_element == target:
            return mid
        elif mid_element < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target_element = 6
result = binary_search(sorted_array, target_element)

if result != -1:
    print(f"Element {target_element} is present at index {result}.")
else:
    print(f"Element {target_element} is not present in the array.")

Output:

Element 6 is present at index 5.

• Time Complexity: The time complexity of binary search is O(log n), where 'n' is the number of elements in the array.

• Space Complexity: The space complexity is O(1), indicating that the memory used by the algorithm remains constant regardless of the input size.

Python Program for Binary Search Using Recursion.

# Python code for Recursive Binary Search Algorithm
def binary_search_recursive(arr, low, high, target):
    if low <= high:
        mid = (low + high) // 2

        # Check if the target is present at the middle
        if arr[mid] == target:
            return mid
        # If the target is smaller, search in the left half
        elif arr[mid] > target:
            return binary_search_recursive(arr, low, mid - 1, target)
        # If the target is larger, search in the right half
        else:
            return binary_search_recursive(arr, mid + 1, high, target)
    else:
        # Target is not present in the array
        return -1

# Example usage:
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 13
result = binary_search_recursive(arr, 0, len(arr) - 1, target)

if result != -1:
    print(f"Element {target} is present at index {result}.")
else:
    print(f"Element {target} is not present in the array.")

Output:

Element 13 is present at index 6.

The base case of the above recursive function is when low is greater than high, indicating that the search range is empty. The function will return the index at which the element is present else it will return -1 which means the target element is not present in the given array.

• Time Complexity: The time complexity is O(log n) because, at each step, the search range is divided by 2.

• Space Complexity: The space complexity is O(log n) due to the recursive call stack.

Binary Search Algorithm with code in C++.

Binary Search is one the most popular and widely used search algorithms used to search whether a particular element is present in the given sorted array or not. It is much better than the Linear search algorithm because it is much faster.  

Problem: Given a sorted array of integers arr[ ] of size n and a target element x, write a C++ program to search the position of x in the given array.

Input: arr[ ] = {7, 10, 11, 15, 20, 30, 26}   x = 20

Output: 4
x is present at index 4.

Input: arr[ ] = {11, 15, 22, 30, 35, 43, 60, 75, 120}   x = 65

Output: -1
x is not present in the arr[ ].

Binary Search Explanation. 

When you try to find the target element in the given array, the worst-case scenario is that when you have to check each element of the given array and it leads to O(n) time complexity. But when the array elements are arranged in sorted order, you can use this extra information to reduce the time complexity to O(log n). 

• If you use a binary search on 100 elements to find your target, the worst-case scenario would be 10 searches. Can you imagine a huge performance improvement? 😲

You get this huge performance improvement because, for each iteration, you reduce the number of elements you will be looking at in half. The idea is to compare the target element to the middle element of the array. 

• If you find the target element is equal to the middle element, return the position of the middle element and stop.
• If the target element is smaller than the middle element, continue searching on the left side of the middle element. high = mid-1
• If the target element is greater than the middle element, continue searching on the right side of the middle element. low = mid+1
• Repeat all three steps until you find the matching element else return -1.

Example: C++ code for Binary Search Algorithm.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int key)
{ 

    int low = 0, high = n - 1; 

    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        //target is found
        if (arr[mid] == key)
        {
            return mid;
        }
        else if (arr[mid] < key) //target might be present in right half
        {
            low = mid + 1;
        }
        else    //target might be present in left half
        {
            high = mid - 1;
        }
    }
    return -1;
}

int main()
{

    int arr[] = {7, 10, 11, 15, 20, 30, 36};
    // size of given array
    int size = sizeof(arr) / sizeof(arr[0]);
    // target element to be find
    int x = 20;

    int index = binarySearch(arr, size, x);
    if (index == -1)
    {
        cout << "Value is not present in the given array." << endl;
    }
    else
    {
        cout << "Value present at index: " << index << endl;
    }
}

Output:

Value present at index: 4

• Time Complexity: O(log n)
• Space Complexity: O(1)

Important points to note: 

int low = 0, high = n - 1;

low and high work like a boundary and we will be looking at elements inside the boundary to find out the target element x and these boundaries get change with each iteration until we found our target loop gets terminated when low == high.

int mid = (high + low) / 2; //formula 1 
int mid = low + (high - low) / 2; //formula 2

Now, a few of you might be thinking that why we are using formula 2 instead of formula 1 as both the formula is going to give the same result? The answer to this question is to avoid integer overflow as the maximum value the integer datatype can hold is 2147483647.  So when you in case of adding two bigger numbers and try to store them in integer datatype it will give you a wrong answer. 

I believe the remaining part of the code was easy to understand with the help of the above explanation and animation gif. If you have any questions or suggestions related to the post, you can share them with us in the comment section below.