Binary Search in minutes

Binary search is an algorithm that returns the index of a given element within a sorted array. To put it simply, it does this by repreatedly halving the list until the number of possible locations of the wanted element is reduced to one.

How binary search works?

1. Say we want to find the position of the element 38 from the following array:
   

2. First we find the midpoint of the array. We can find the midpoint by using the formula mid = (low + high) / 2.
   

3. Compare 38 with the middle element. Since 25 is less than 38, we omit the first half. For the second half, low = mid + 1.
   

4. Repeat until mid points to the target element and return the index, which in this case is 6.
   

Implementation in Python

# iterative approach
def iterative_binary_search(list, target):
    low = 0
    high = len(list) - 1

    while high > low:
        mid = math.floor((low + high) / 2)
        if list[mid] == target:
            return mid
        elif list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# recursive approach
def recursive_binary_search(list, target, low, high):
    if low < high:
        mid = math.floor((low + high) / 2)

        if list[mid] == target:
            return mid
        elif list[mid] < target:
            return recursive_binary_search(list, target, mid + 1, high)
        else:
             return recursive_binary_search(list, target, low, mid - 1)

    return -1

Time complexity of binary search

• Best case is when target element is positioned exactly in the middle.
• Number of elements = 2^depth because each element branches into 2 more elements.
• Worst case is when the searches the deepest level of the tree.
• Depth is approximately log₂n, where n is the number of elements.

Space complexity of binary search

• Iterative binary search requires three pointers(to keep track of the starting, middle and end points) regardless of the size of the array. Hence, its space complexity of is O(1).

• On the other hand, recursive binary search does not have any loops and the new values are passed onto the next recursive call. The time complexity for recursive binary search is O(log n).