Mastering Binary Search and Its Variations

Binary Search Fundamentals

Binary search is one of the most important algorithms in computer science. It efficiently finds a target value in a sorted array by repeatedly dividing the search space in half. Time complexity is O(log n), making it extremely fast even for large datasets.

Classic Implementation

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

# Time: O(log n), Space: O(1)

Finding First/Last Occurrence

When array contains duplicates, you might need the first or last occurrence of target.

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

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

Binary Search on Answer Space

Advanced technique where you search possible answers rather than array indices. Useful for optimization problems with monotonic properties.

# Find minimum in rotated sorted array
def find_min_rotated(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] > arr[right]:
            left = mid + 1
        else:
            right = mid
    return arr[left]

# Ship packages within D days
def ship_within_days(weights, days):
    def can_ship(cap):
        cur, d = 0, 1
        for w in weights:
            if cur + w > cap:
                d += 1
                cur = w
            else:
                cur += w
        return d <= days
    left, right = max(weights), sum(weights)
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1
    return left

Common Variations

Search in Rotated Sorted Array uses modified binary search handling rotation point. Find Peak Element finds element greater than neighbors. Sqrt(x) searches answer space [0, x]. Koko Eating Bananas minimizes eating speed. Median of Two Sorted Arrays uses partition technique.

Tips

Always use mid = left + (right - left) // 2 to avoid overflow. Be careful with loop conditions. Test edge cases: empty array, single element, target at boundaries. Draw out the search space to visualize pointer movement.