Classic Binary Search on a Sorted Array

Classic binary search finds an index or proves absence in O(log n) steps. The key is: each comparison removes about half of the remaining indices.

Try this in Python

def first_index_ge(sorted_arr: list[int], x: int) -> int | None:
    """First index with value >= x, or None if all smaller."""
    lo, hi = 0, len(sorted_arr) - 1
    ans = None
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_arr[mid] >= x:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans


print(first_index_ge([2, 4, 4, 7], 5))

Key takeaways

• Same loop, different move rule depending on what you minimize/maximize.
• Draw tiny arrays on paper before coding.
• Always test len==0 and len==1.