Binary Search

Binary search is an efficient algorithm for finding an item in a sorted array. It works by repeatedly dividing the search interval in half.

Algorithm

Given a sorted array $A$ and a target value $x$:

1. Compare $x$ with the middle element
2. If $x$ matches the middle element, return its index
3. If $x$ is greater than the middle element, search the right half
4. If $x$ is less than the middle element, search the left half
5. Repeat until the element is found or the search space is exhausted

Time Complexity

Binary search has a time complexity of $O(\log n)$, where $n$ is the number of elements in the array.

Implementation

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Return -1 if the target is not found

# Example usage with a sorted array
arr = [12, 23, 34, 45, 56, 78, 89]
target = 56
result = binary_search(arr, target)

if result != -1:
    print("Element {} found at index {}.".format(target, result))
else:
    print("Element {} not found in the array.".format(target))

Exercises

A full exercise set is available for this topic, structured as one worked example + 7 practice problems (across 7 surface contexts) + 2 pattern-resistant check problems.