Binary Search

Binary search is an efficient recursive Search algorithms that allows to find an item $x$ into a sorted sequence $seq$ in $O(logn)$ time.

The idea of the algorithm is to check the element in the middle. If this element is $x$, then we return the position, else we check the left part if $x$ is lower, or the right part if $x$ is higher.

When the subsequence we are examining has length of 1, we return the index if the element is the same, otherwise we return a special symbol (like None) to signal that the item wasn’t found.

def binary_search(seq, x, low=0, high=None):
    # If this is the first call, set high to the length of the sequence
    if high is None:
        high = len(seq) - 1
    # Base case: if the search space is exhausted, return None (not found)
    if low > high:
        return None
 
    # Find the middle index
    mid = (low + high) // 2
 
    # Check if the middle element is the target
    if seq[mid] == x:
        return mid
    # If the target is smaller, search in the left half
    elif seq[mid] > x:
        return binary_search(seq, x, low, mid - 1)
    # If the target is larger, search in the right half
    else:
        return binary_search(seq, x, mid + 1, high)

---

tags:#algorithms related: Binary Search Approach