Binary Search — Classic Exact Target [LC 704, FAANG O(log n) Interview]

Problem Statement#

Given a sorted array of distinct integers nums and an integer target, return the index of target if it exists, or -1 otherwise. The algorithm must run in O(log n).

Constraints:

• 1 lessequal nums.length lessequal 10^4
• -10^4 lt nums[i], target lt 10^4
• All integers in nums are unique and sorted ascending

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

Why This Problem Matters#

LC 704 is the single most foundational binary search interview problem. Engineers at Google, Amazon, Meta, Apple, and Microsoft are asked binary search questions in nearly every algorithmic round, and LC 704 is the warm-up that gates everything harder. The reason is not the algorithm itself — linear search on a sorted array is trivially correct. The reason is what binary search teaches: structure in data enables logarithmic exploration.

Once you internalise that idea, you unlock dozens of harder problems — searching rotated arrays, finding first and last positions, binary search on an answer space, peak finding. Every one of them descends from the 15 lines you write for LC 704. This is why the FAANG O(log n) interview funnel almost always starts here.

Interviewers also use this problem to screen three things: can you recognise that sorted structure implies a binary decision at every step, can you handle off-by-one boundary conditions cleanly, and can you state the loop invariant out loud. Candidates who reach for an O(n) scan when the input is sorted get redirected immediately.

The Core Insight#

A sorted array lets you make a definitive decision at every midpoint. Pick the element at the exact middle of the current search range. Three outcomes are possible: equal returns the index, smaller means the target is to the right, larger means the target is to the left. Each step eliminates half the remaining candidates, so after log2(n) steps the answer is found or the range is empty.

The invariant: if the target exists, it lies within [lo, hi]. When lo gt hi, the range is empty and the target is absent. One critical implementation detail — compute the midpoint as lo + (hi - lo) / 2, not (lo + hi) / 2, to avoid integer overflow in static-typed languages.

Visual Dry Run#

For target = 2 (absent):

Solution (Optimal)#

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1          # inclusive bounds
        while lo <= hi:                     # search space non-empty
            mid = lo + (hi - lo) // 2      # overflow-safe midpoint
            if nums[mid] == target:
                return mid                  # exact match
            elif nums[mid] < target:
                lo = mid + 1               # target is to the right
            else:
                hi = mid - 1               # target is to the left
        return -1                           # exhausted, not present

var search = function(nums, target) {
    let lo = 0;
    let hi = nums.length - 1;              // inclusive upper bound
    while (lo <= hi) {                      // loop while space non-empty
        const mid = lo + Math.floor((hi - lo) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            lo = mid + 1;                  // target to the right
        } else {
            hi = mid - 1;                  // target to the left
        }
    }
    return -1;                              // not found
};

Time: O(log n) — halves search space each iteration, at most ceil(log2(n)) comparisons. Space: O(1) — only three integer variables.

Common Mistakes#

• Using (lo + hi) / 2 in Java/C++ overflows for large arrays; always subtract.
• Writing while lo lessequal hi with hi = mid instead of mid - 1 causes infinite loops at lo == hi.
• Off-by-one in initial bounds — hi = len(nums) instead of len(nums) - 1 triggers index-out-of-bounds.
• Confusing this with the left-boundary template — they use different loop conditions.
• Adding an early return -1 inside the else branch — the loop handles exhaustion naturally.

Interview Tips#

• State the invariant aloud: "if target exists, it lies within [lo, hi]."
• Mention the overflow-safe midpoint even when writing Python.
• Walk through one found and one not-found example in your dry run.
• Point out the empty-array edge case: hi = -1 means the loop never executes.
• Distinguish this template from left-boundary before writing code.

Follow-up Questions#

• What if the array contains duplicates? Classic search finds some occurrence; for first or last, use boundary variants — see LC 34.
• Can you implement this recursively? Yes, but space becomes O(log n) due to call stack — iterative preferred.
• What if the array is sorted descending? Flip the comparison directions inside the if/else.
• How do you adapt this for a rotated sorted array? See LC 33 — check which half is sorted before deciding direction.
• For n equal one million, how many comparisons in the worst case? ceil(log2(10^6)) = 20.

Key Takeaways#

• Binary search makes a three-way decision at every midpoint: equal, smaller, larger.
• The loop invariant guarantees the target always lies inside [lo, hi] if it exists.
• Use lo + (hi - lo) / 2 to compute the midpoint and avoid 32-bit overflow.
• The classic template pairs while lo lessequal hi with hi = mid - 1 and lo = mid + 1.
• Loop terminates when lo gt hi (empty range) or when the target is found.
• Worst case is ceil(log2(n)) comparisons — 20 for one million elements, 30 for one billion.
• Mastering this 15-line template is the foundation for every FAANG binary search variant.