Binary Search (LeetCode 704): The Foundation

Binary Search is LeetCode problem 704, and it is about as pure as algorithm problems get. No tricks, no edge cases hiding behind a story problem. Just: given a sorted array and a target, find the target or return -1.

It is also one of the most commonly botched problems in interviews. Not because people do not understand the concept, but because they get the bounds wrong and either loop forever or skip the answer. Let's make sure that does not happen to you.

The problem

Given a sorted (ascending) array of integers nums and an integer target, write a function to search for target in nums. If target exists, return its index. Otherwise, return -1.

Example: nums = [-1, 0, 3, 5, 9, 12], target = 9. The answer is 4 because nums[4] = 9.

You must write an algorithm with O(log n) runtime complexity. That rules out linear scan. Binary search is the intended approach.

Why not just loop through it?

You could iterate through the array and check every element. That works, and it is O(n). But the problem explicitly requires O(log n), which means you need to eliminate half the search space at each step.

The array is sorted, so you can do exactly that. Pick the middle element. If it equals the target, you are done. If the target is larger, the answer must be in the right half. If the target is smaller, the answer must be in the left half. Repeat until you find it or run out of elements.

Visual walkthrough

Let's search for 9 in [-1, 0, 3, 5, 9, 12]. Watch how the search space shrinks with each comparison.

Two steps. Out of 6 elements, we only checked 2. For larger arrays the savings are dramatic: a million elements takes at most 20 checks.

The code

Here is the clean Python solution for LeetCode binary search:

def search(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1

Let's walk through each piece:

• lo, hi = 0, len(nums) - 1 sets up the search range as the full array. Both lo and hi are inclusive bounds.
• while lo <= hi keeps going as long as there is at least one element in the search range. When lo passes hi, the range is empty and the target is not in the array.
• mid = lo + (hi - lo) // 2 computes the middle index. We use this form instead of (lo + hi) // 2 to avoid integer overflow in languages like Java and C++. In Python it does not matter, but it is a good habit.
• if nums[mid] == target: return mid is the success case. We found it.
• lo = mid + 1 moves the left boundary past mid, eliminating the left half including mid itself.
• hi = mid - 1 moves the right boundary before mid, eliminating the right half including mid.
• return -1 means we exhausted the search space without finding the target.

When to use < vs <=

This is the single most common source of confusion with binary search. Let's clear it up.

while lo <= hi (inclusive bounds)

Both lo and hi are valid indices. The search space is [lo, hi]. When lo == hi, there is one element left to check. The loop exits when lo > hi, meaning the search space is empty.

This is the version you should use for LeetCode 704. You initialize hi = len(nums) - 1 (last valid index), and you update with lo = mid + 1 and hi = mid - 1.

while lo < hi (left-closed, right-open or converging)

The loop exits when lo == hi, meaning the two pointers have converged to a single candidate. This version is common for "find the first/last element that satisfies a condition" variants, where you do not return early on a match.

If you use < with the standard return-on-match template, you will skip checking the last remaining element and potentially miss the answer. If you use <= with a convergence template, you risk an infinite loop.

The rule: match your loop condition to your update logic. For this problem, <= with mid + 1 / mid - 1 updates is the cleanest approach.

Common off-by-one mistakes

Binary search is notorious for subtle boundary bugs. Here are the ones that show up over and over.

1. Setting lo = mid or hi = mid instead of mid + 1 / mid - 1.

If lo == hi == mid, setting lo = mid does not make progress and you loop forever. You have already checked mid, so you must exclude it from the next iteration.

2. Using the wrong loop condition for your template.

As discussed above, < and <= have different semantics. Mixing them with the wrong update logic is the most common binary search bug. If you use <=, update with mid + 1 and mid - 1. If you use <, make sure you understand which pointer to update and how.

3. Off-by-one on hi initialization.

If hi = len(nums) (one past the end) instead of hi = len(nums) - 1, you could read out of bounds when checking nums[hi] or nums[mid]. With inclusive bounds, always use len(nums) - 1.

4. Returning -1 too early.

Some people add an early return inside the loop for "optimization" (like checking if target < nums[lo]). This is unnecessary and error-prone. Let the loop handle the narrowing naturally.

Complexity analysis

Time: O(log n). Each iteration cuts the search space in half. Starting with n elements, after k iterations we have n / 2^k elements left. The loop ends when this reaches 0, so k = log2(n). For an array of 1,000,000 elements, that is about 20 iterations.

Space: O(1). We use three variables (lo, hi, mid) regardless of input size. No extra data structures, no recursion stack.

This is optimal. You cannot find an element in a sorted array faster than O(log n) in the comparison model, and you cannot use less than O(1) space.

The Building Blocks

The LeetCode binary search solution is built from one core building block:

Search space halving. The idea of maintaining an inclusive range [lo, hi], computing a midpoint, and eliminating half the range based on a comparison. This exact mechanism is the engine behind a huge family of problems:

• Search Insert Position: same template, but return lo instead of -1 when the target is not found
• First Bad Version: binary search where the comparison is a function call instead of an array lookup
• Find Peak Element: the "sorted" structure is a local monotonicity condition rather than a globally sorted array
• Search in Rotated Sorted Array: binary search with an extra check to determine which half is actually sorted
• Koko Eating Bananas: binary search on the answer space, where you search over possible speeds instead of array indices

In every case, the core loop is the same. You narrow [lo, hi] until you find the answer or the range is empty. What changes is the comparison logic and what you do when the loop ends.

Once you can write the basic binary search template from memory without any hesitation, these harder variants become straightforward modifications. You are not solving a new problem each time. You are plugging a new comparison into the same skeleton.

Problems that use the same brick

Once you have search space halving locked in, try these:

• Search Insert Position: the simplest extension, return the insertion index for a missing target
• First Bad Version: left-bound binary search with a boolean predicate
• Find Minimum in Rotated Sorted Array: binary search on a rotated structure
• Search a 2D Matrix: flatten the 2D grid conceptually and binary search on it
• Koko Eating Bananas: binary search on the answer space, a completely different framing of the same template

Why you will forget this (and how to fix it)

Binary search feels trivial right now. "Obviously you set lo and hi, obviously you check mid, obviously you update with mid + 1 and mid - 1." But three weeks from now, under interview pressure, there is a real chance you second-guess yourself. Was it lo <= hi or lo < hi? Do I return lo or hi or mid after the loop? Do I set hi = mid or hi = mid - 1?

These are not hard questions. But under pressure, with an interviewer watching, small doubts compound. You write the wrong condition, get an infinite loop on the test case, panic, and burn five minutes debugging something you "knew."

Spaced repetition solves this. You type the solution from scratch today, then again tomorrow, then in three days, then a week. Each time from memory, not from a reference. After a few rounds, the template is locked in permanently. You write lo <= hi and mid + 1 / mid - 1 without thinking, and you save your brainpower for the parts of harder problems that actually require thought.

Related posts

• Binary Search: More Than Finding a Number - The full guide to binary search patterns, including left-bound/right-bound variants and searching on the answer space
• Two Sum: The Classic Interview Starter - Another foundational problem that teaches the hash map complement lookup pattern

---

Visual Learner? See binary search in action step-by-step with our Binary Search Interactive Visualization.