Binary Search: The Matrix of Algorithms – Patterns, Edge Cases, and Real Interview Questions

The Quest Begins (The "Why")

I still remember the first time I bombed an interview because I tried to solve a “find the target in a sorted array” question with a simple loop. The interviewer raised an eyebrow, I felt the sweat start, and I walked out thinking I’d just missed a easy win. Later, after a few more rejections, I realized I was treating every sorted list like a maze I had to wander through step‑by‑step. That’s when I stumbled upon binary search – the algorithm that feels like Neo dodging bullets in slow motion. It turned a frustrating O(n) slog into a crisp O(log n) victory, and I’ve been hooked ever since.

Why does it feel like magic? Because instead of checking each element, we repeatedly cut the problem in half. If you know the array is sorted, you can instantly discard half of the possibilities with a single comparison. It’s the same idea you use when looking up a word in a dictionary: you open to the middle, see if your word comes before or after, and then ignore the half that can’t possibly hold it. Over and over, the search space shrinks exponentially, and you land on the answer (or confirm it’s not there) in just a handful of steps.

The Revelation (The Insight)

The secret sauce isn’t just “pick the middle”; it’s the invariant we maintain throughout the loop. At any point, we keep two indices, low and high, that guarantee the target—if it exists—lies somewhere between them. When we compute mid = low + (high - low) // 2, we’re not picking a random spot; we’re picking the exact middle of the current viable range. Then we compare arr[mid] to the target:

• If they’re equal, we’ve found it.
• If arr[mid] is less than the target, the target can’t be in the left half (including mid) because everything there is too small. So we move low to mid + 1.
• If arr[mid] is greater than the target, the target can’t be in the right half (including mid) because everything there is too large. So we move high to mid - 1.

Each iteration halves the viable interval, guaranteeing that after at most ⌈log₂(n+1)⌉ checks we either find the target or exhaust the interval (low > high). That’s why the runtime is O(log n) and the space usage is O(1) – no recursion stack needed if we write it iteratively.

What blew my mind the first time I saw it was how robust this simple idea is. It works on any monotonic predicate, not just plain equality searches. Think “find the first bad version” or “find the smallest element ≥ x”. The same loop skeleton applies; you only change the condition that decides which half to discard.

Wielding the Power (Code & Examples)

Before: The Linear Struggle

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Fine for tiny arrays, but on a million‑item list you’ll do up to a million comparisons in the worst case. In an interview, that’s a red flag.

After: Binary Search – The Clean Spell

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2   # avoids overflow in other languages
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1               # discard left half
        else:
            high = mid - 1              # discard right half
    return -1

Why this works: The loop invariant (target is in arr[low:high+1]if it exists) holds true before the first iteration (whole array) and is preserved by each branch. When the loop ends,lowhas passedhigh`, meaning the interval is empty – the target isn’t present.

Common Trap #1 – Off‑by‑One Errors

A frequent mistake is setting high = mid instead of high = mid - 1 when arr[mid] > target. That can cause an infinite loop when the target is not in the array because the interval never shrinks. Always move the bound past the middle element you’ve just examined.

Common Trap #2 – Integer Overflow (in languages like Java/C++)

mid = (low + high) // 2 can overflow when low and high are both large. Using low + (high - low) // 2 is safe and worth mentioning in an interview to show you care about edge cases.

Real Interview Problem #1 – Search in a Rotated Sorted Array

You’re given a sorted array that has been rotated at an unknown pivot (e.g., [4,5,6,7,0,1,2]). Find the index of a target value in O(log n) time or return -1 if it’s not there.

Approach: Even though the array isn’t fully sorted, one half of any mid split will always be sorted. We can decide which half to keep based on where the target lies relative to that sorted half.

`python
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid

    # Determine which side is properly sorted
    if nums[lo] <= nums[mid]:          # left half is sorted
        if nums[lo] <= target < nums[mid]:
            hi = mid - 1               # target in left half
        else:
            lo = mid + 1               # target in right half
    else:                               # right half is sorted
        if nums[mid] < target <= nums[hi]:
            lo = mid + 1               # target in right half
        else:
            hi = mid - 1               # target in left half
return -1

`

The same binary‑search skeleton shines here; we just add a extra check to see which side is monotonic.

Real Interview Problem #2 – First Bad Version (LeetCode 278)

You have versions [1..n]. A bad version causes all later versions to be bad. Implement firstBadVersion(n) that minimizes calls to the API isBadVersion(version).

python
def firstBadVersion(n):
lo, hi = 1, n
while lo < hi:
mid = lo + (hi - lo) // 2
if isBadVersion(mid):
hi = mid # mid could be first bad
else:
lo = mid + 1 # mid is good, look right
return lo # lo == hi is the first bad


Notice we stop when lo == hi; the invariant is that the first bad version lies in [lo, hi].

Why This New Power Matters

Mastering binary search does more than let you ace a coding interview. It teaches you to think in terms of invariants and divide‑and‑conquer—skills that transfer to everything from optimizing database queries to designing efficient UI search widgets. Suddenly, problems that felt like “scan the whole list” become opportunities to cut the work in half, again and again, until you’re left with a trivial answer.

And the best part? The pattern is tiny enough to fit on a sticky note, yet powerful enough to unlock entire families of challenges: finding bounds, counting occurrences, solving monotonic predicate problems, and even tackling two‑pointer tricks that rely on the same halving logic.

Your Next Quest

Here’s a challenge to solidify the spell: Implement a function that finds the square root of an integer x (rounded down) using only binary search. No built‑in sqrt, no floating‑point tricks—just pure integer search on the range [0, x]. Drop your solution in the comments or tweet it with #BinarySearchQuest. I can’t wait to see how you wield this new power!

Happy hunting, and may your logs always be base 2! 🚀