Binary Search: The Algorithm You Must Know

Understanding O(log n)

Binary search works by repeatedly dividing the search interval in half. It only works on sorted arrays. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half.

Implementation in Python

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Common Pitfalls

The most common bug is calculating the midpoint. In languages with fixed-size integers (like C++ or Java), (left + right) / 2 can overflow. Python handles large integers automatically, so this is safer.