Pro

Binary Search: A Complete Crash Course

Binary search finds a target in a sorted array by checking the middle element and discarding the half that cannot contain the target. It runs in O(log n) time.

Each step works like this:

  • If the middle value is too large, keep searching the left half
  • If the middle value is too small, keep searching the right half
  • If the middle value equals the target, you are done

The only requirement is that the search space is sorted, or at least ordered in a way that tells you which half to drop. It does not have to be an array at all.

2) Duplicates

Without duplicates, any index holding the target is the answer. With duplicates, a plain search may land on any copy.

Ask your interviewer which copy they want: the first one, the last one, or any of them. That choice decides which variation of binary search you write.

Every variation uses the same loop. Only the comparison and the pointer you move change.

Classic search returns as soon as it finds the target.

Leftmost occurrence keeps moving right toward the target and ends on its first copy.

Rightmost occurrence keeps moving left past the target and ends just after its last copy.

Search on a range looks for the smallest or largest value that satisfies a condition, even when there is no array.

Once you see binary search as "find the boundary where a condition flips", it shows up in many problems that never mention sorting:

  • Searching a sorted matrix
  • Finding a peak element
  • Square roots
  • Minimum speed or capacity problems

NOTES

Avoid overflow:

  • In Java and C++, compute mid = left + (right - left) / 2. Python integers do not overflow, so (left + right) // 2 is fine.

Watch the loop:

  • Decide whether the loop condition is left <= right or left < right, and update the pointers to match, or the search can run forever.

Binary Search

Finds a target in a sorted array in O(log n) time by halving the search space every step.

target = 9

  • Middle too small: drop the left half
  • Middle too large: drop the right half
  • Middle equals target: return it

The input only has to be ordered, so binary search also works on ranges of numbers, not just arrays.

Duplicates

With no duplicates, there is exactly one index to return.

With duplicates, the middle might land on any copy of the target:

Ask which copy the problem wants before writing any code.

Computing mid safely

  • Java and C++: left + (right - left) / 2 avoids integer overflow
  • Python: (left + right) // 2 is fine because integers grow as needed

Four Ways to Binary Search

Same loop, different comparison. Pick the one that matches what the problem asks for.

Classic

Search a sorted array and return the index of the target, or -1.

while lo <= hi:
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
return -1
  • Use it when you only need to know whether the target exists
  • Ask yourself: is this exact value here?

Finding 9

Leftmost Occurrence

Return the first index whose value is at least the target.

lo, hi = 0, len(nums)
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid
return lo   # first copy, if it exists
  • Use it for the left boundary of a run of duplicates
  • Ask yourself: where does this value start?

First 4 is at index 1

Rightmost Occurrence

Return the index just past the last copy of the target.

lo, hi = 0, len(nums)
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] <= target:
        lo = mid + 1
    else:
        hi = mid
return lo - 1   # last copy, if it exists
  • Pairs with the leftmost search to count copies
  • Ask yourself: where does this value end?

Last 4 is at index 3

Search a Range

Find the smallest value in a range that makes a condition true.

lo, hi = low_limit, high_limit
while lo < hi:
    mid = (lo + hi) // 2
    if works(mid):
        hi = mid        # mid works, try smaller
    else:
        lo = mid + 1
return lo
  • There may be no array at all, only a range of candidate answers
  • Ask yourself: what is the smallest value that works?

Smallest value that works: 4