Classic Binary Search: Left, Right, Mid

Binary search reduces an O(n) linear scan to O(log n) by halving the search space at every step. In an array of one million elements a linear scan needs up to 1,000,000 comparisons, but binary search needs at most 20. This efficiency makes it one of the most commonly tested algorithms in coding interviews.

The core insight is that a sorted array lets you decide, after a single comparison, which half of the remaining data to discard entirely.

Binary search uses three index pointers: lo (left boundary), hi (right boundary), and mid (midpoint). At each iteration you compute mid = (lo + hi) // 2 and compare the target against arr[mid]. If the target is smaller, move hi = mid - 1; if larger, move lo = mid + 1; if equal, you found it.

The loop continues while lo <= hi. When the loop exits without finding the target, return -1.

The expression mid = (lo + hi) // 2 can cause integer overflow in languages with fixed-width integers (Java, C++). Python integers are arbitrary-precision so overflow never occurs, but interviewers still expect you to know the safe alternative: mid = lo + (hi - lo) // 2.

This form computes the same midpoint but adds only the half-distance to lo rather than summing both pointers first. Mentioning this in an interview signals awareness of low-level concerns.

One of the trickiest parts of binary search is choosing whether hi points to the last valid index (inclusive, hi = len(arr) - 1) or one past the end (exclusive, hi = len(arr)). Different conventions require different loop conditions and boundary updates.

With inclusive boundaries use while lo <= hi and update hi = mid - 1. With exclusive boundaries use while lo < hi and update hi = mid. Mixing conventions is the single most common source of bugs in binary search implementations.

Binary search can be written recursively by passing updated lo and hi bounds through the call stack. Each recursive call reduces the search space by half, so the depth is O(log n). The base case is when lo > hi (not found) or arr[mid] == target (found).

The iterative version is preferred in production code because it avoids stack-frame overhead, but the recursive version communicates the divide-and-conquer structure more clearly on a whiteboard.

Robust binary search must handle edge cases without crashing. The three most common are: an empty array (the loop never executes and -1 is returned correctly), a single-element array (mid equals lo equals hi, one comparison suffices), and targets outside the range (lo eventually exceeds hi and -1 is returned).

Always verify your implementation against these inputs before moving to follow-up questions in an interview.

Binary search has O(log n) time complexity because each comparison halves the search space. After k comparisons the remaining space is n/2^k; the search ends when this reaches 1, so k = log₂ n.

Space complexity is O(1) for the iterative version (only three integer variables) and O(log n) for the recursive version due to the call stack depth. In an interview always state both and prefer the iterative form when space is constrained.

Classic binary search returns any index where the target exists. But many interview problems ask for the first or last occurrence of a target. For those you must continue searching even after finding a match — instead of returning immediately, narrow the boundary and keep going.

When searching for the first occurrence, after finding arr[mid] == target, record mid as a candidate and set hi = mid - 1. For the last occurrence set lo = mid + 1.

Python's standard library provides bisect.bisect_left(arr, x) and bisect.bisect_right(arr, x) for production-ready binary search. bisect_left returns the leftmost index where x can be inserted to keep the array sorted, effectively finding the first position where arr[i] >= x.

Interviewers may allow you to use bisect; always confirm first. Knowing how it works under the hood (it is O(log n) binary search) is still essential.

Three mistakes cause most binary search bugs in interviews. First, wrong loop condition: using < instead of <= with inclusive boundaries causes the last remaining element to be skipped. Second, incorrect boundary update: forgetting the +1 or -1 creates an infinite loop when lo == hi. Third, operating on an unsorted array: binary search is only correct on sorted data.

Before writing any binary search, state aloud: 'The array is sorted, my boundaries are inclusive, and my loop runs while lo <= hi.'

When you see a problem on a sorted array, a monotonically increasing function, or a search space that can be halved, immediately consider binary search. In an interview, narrate your thinking: 'Since the array is sorted, I can discard half the elements per comparison, giving O(log n).'

Always verify your solution on at least three inputs: a value at the start, a value at the end, and a value that is absent. Stating complexity proactively — 'time O(log n), space O(1)' — before being asked signals strong fundamentals.

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

In this lesson you learned: binary search halves the search space each step for O(log n) time, the inclusive boundary convention uses lo <= hi with updates lo = mid+1 and hi = mid-1, and to find first/last occurrences you continue searching after a match rather than returning immediately. Next up we explore how binary search extends to rotated and unsorted arrays.