Binary Search Algorithm

Abstract

A Binary Search Algorithm is a type of Searching Algorithm that is pretty efficient and useful to use. It lowers the time complexity to $\theta(\log n)$ as compared to a linear search of $\theta (n)$ where $n$ is the size of the input.

There are multiple forms of Binary Search but they are all similar to one another. There is the iterative and recursive version of this algorithm. In this short post, both versions of the searching algorithm will be depicted in Python.

Note that for this searching algorithm to work, the array must be sorted.

Code

Iterative

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def iterativeBinarySearch(array, value):
    left = 0
    right = len(array)

    while left <= right:
        mid = (left + right) >> 1
        if array[mid] == value:
            return mid
        elif array[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1

This function returns the mid point if the value to find is equal to the middle value, it returns a -1 if the value is not found (Value not in array).

The binary search algorithm effectively cuts the search space by half at every iteration, this lowers the time complexity of this algorithm.

Recursive

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def recursiveBinarySearch(array, value, left, right):
    if left > right:
        return -1

    mid = (left + right) >> 1
    if array[mid] == value:
        return mid
    elif array[mid] < value:
        return recursiveBinarySearch(array, value, mid + 1, right)
    else:
        return recursiveBinarySearch(array, value, left, mid - 1)

This is the recursive version of the Binary Search Algorithm. The base case is when left > right, this means that the left pointer is higher than the right pointer. This would trigger if the value to find is not in the array and this would return -1.

Similar to the iterative version of the algorithm, we will find the middle index followed by checking if the middle element (array[mid]) is the value to find, returning the value of mid if it is.

Next, according to similar conditions to the iterative version, this will either update the left pointer to mid + 1 or the right pointer to mid - 1 accordingly. This function will then be called recursively to search for the value.

The Program

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def iterativeBinarySearch(array, value):
    left = 0
    right = len(array)

    while left <= right:
        mid = (left + right) >> 1
        if array[mid] == value:
            return mid
        elif array[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def recursiveBinarySearch(array, value, left, right):
    if left > right:
        return -1

    mid = (left + right) >> 1
    if array[mid] == value:
        return mid
    elif array[mid] < value:
        return recursiveBinarySearch(array, value, mid + 1, right)
    else:
        return recursiveBinarySearch(array, value, left, mid - 1)


array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(iterativeBinarySearch(array, 10))
print(recursiveBinarySearch(array, 4, 0, len(array) - 1))

1
2
3

# Outputs:
9
3

Conclusion

This is a rather interesting and efficient searching algorithm that may be useful for searching for values in an array and can be adapted to search for values in other data types as well and for all other different applications. This algorithm will search for the required values much faster than a normal iterative search would, reducing the amount of time required to search for a value.

Do note the line to get the mid value:

1

mid = (left + right) >> 1

This is a slightly more efficient method to divide by 2, the notation >> 1 is a right shift operator that divides by $2^n$ where $n$ is the value 1 in this case. This is equivalent to this line:

1
2

mid = (left + right) // 2 # Floor Division
mid = (left + right) / 2  # Division

There are 2 posts on this searching algorithms on this site here: Leetcode Binary Search and Leetcode First Bad Version 278