Python program for binary search

In this tutorial, we will learn what is binary searching techniques and how they can be implemented in python programs.

Binary means to bisect or to divide the object into two-part, so it is easy to understand that binary searching means we will search the required element in the array or list by breaking the array into smaller two parts.

The important thing to remember is that we can only apply binary search if the list or array is sorted otherwise not.

As the output, we are required to get the index number of the element if it is present in the array otherwise -1 if not present.

Look at the given example to understand the working with input and output. Consider the element to be searched is "x".

Input:

array: 3 5 1 2 6

x: 2

Output: 3

Input:

array: 56 9 11 7 60

x: 44

Output: -1

Binary search

Binary search can be implemented using two different approaches that are as follows:

1. Iterative method

2. Recursive method

The recursive method uses the divide and conquer rule, however, the basic algorithm for both is the same.

Binary search Algorithm

Step 1: Place two pointers at the lowest (starting point) and highest (ending point) positions in the array and name them as "low" and "high" respectively.

Step 2: Evaluate middle position as mid=(low+high)/2.

Step 3: Now if x==mid, simply return mid. If x is not equal to mid, then compare it with mid accordingly.

Step 4: If x>mid, this means that the required element can never be present on the left side of mid. Reassign the value of "low" as low=mid+1 and start the comparison with the new value of mid.

Step 5: Else x<mid, this means that the required element can never be present on the right side of mid, now put high=mid-1.

Step 6:Repeat the steps from 3 to 5 until low meets high.

Step 7: If low becomes greater than high, then return -1. This means the element that we are searching for is not present in the given array.

Binary search Python program 1 (Iterative method)

# Binary Search in python


def binarySearch(array, x, low, high):

    # Repeat until the pointers low and high meet each other
    while low <= high:

        mid = low + (high - low)//2

        if array[mid] == x:
            return mid

        elif array[mid] < x:
            low = mid + 1

        else:
            high = mid - 1

    return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Element is present at index 1

Binary search Python program 2 (Recursive method)

# Binary Search in python


def binarySearch(array, x, low, high):

    if high >= low:

        mid = low + (high - low)//2

        # If found at mid, then return it
        if array[mid] == x:
            return mid

        # Search the left half
        elif array[mid] > x:
            return binarySearch(array, x, low, mid-1)

        # Search the right half
        else:
            return binarySearch(array, x, mid + 1, high)

    else:
        return -1


array = [3, 4, 5, 6, 7, 8, 9]
x = 4

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Not found")

Element is present at index 1

Conclusion

In this tutorial, we have seen one of the most popular searching techniques i.e. binary search using iterative and recursive approaches.