Binary Search
Binary Search is LeetCode 704 (Easy). You are given an integer array nums sorted in ascending order, with no repeated values, and an integer target. Return the index of target in nums, or -1 if it is not there.
The solution must run in O(log n) time, so a linear scan that checks every element is not accepted.
- 1 <= nums.length <= 10⁴
- -10⁴ < nums[i], target < 10⁴
- All integers in nums are unique
- nums is sorted in ascending order
Intuition
Because the array is sorted, one comparison removes half of it. If the middle element is smaller than the target, everything to its left is smaller too and can be discarded; if it is larger, everything to its right can go. Either way, the part that could still hold the target halves.
That halving is the whole algorithm, and it sets the running time: n elements are settled in about log₂ n comparisons, so a million elements need only 20. The idea is simple; the difficulty is bookkeeping, keeping the window boundaries consistent so no element is skipped and the loop always ends.
A sorted array (or any ordered search space) plus a test that tells you which side the answer is on. That test does not have to be nums[mid] < target; any yes/no condition that flips once from false to true can be searched the same way, which is how capacity and speed problems become binary search on the answer.
Approach
Before reading on, decide: is hi the last index or one past it? What must the loop condition be for that choice? What happens with a single-element array?
Two ways to solve it
Halve the window [lo, hi] inside a while loop until the target is found or the window is empty.
- Space: just
lo,hiandmid. - Speed: no function call per step.
- Safety: no recursion limit to hit.
The version to write in an interview.
A helper find(lo, hi) checks the middle and calls itself on the half that can still hold the target.
- Space: one stack frame per halving.
- Speed: same comparisons, plus a call each step.
- Reads like: the textbook definition.
Good for understanding; no gain over the loop.
Both make the same comparisons, so only memory differs, and the loop needs none. The steps, code and live demo below follow the iterative version; the recursive code comes after the demo.
Keep a closed window [lo, hi]
Start with lo = 0 and hi = len(nums) - 1, both inclusive. The invariant is: if the target exists, its index is in [lo, hi]. Every later update is chosen to keep that sentence true, which is how you know each move is safe.
Loop while the window is not empty
Use while lo <= hi. When lo == hi there is still one unchecked element, so < would skip it. When lo > hi the window is empty and the target is absent.
Compute the middle without overflow
mid = lo + (hi - lo) // 2. In C++ and Java, (lo + hi) / 2 can exceed the 32-bit range and become negative; the subtraction form never overflows.
Compare and discard a half
nums[mid] == target: returnmid.nums[mid] < target:lo = mid + 1.nums[mid] > target:hi = mid - 1.
Always move past mid; it has already been checked, and keeping it can make the loop run forever.
Return -1 after the loop
If the loop ends without returning, the window is empty and every index has been ruled out, so return -1. The invariant guarantees this is right: the target would have stayed inside the window, and nothing is left there. This iterative version needs only O(1) extra space.
Binary Search solution in Python | C++ | Java
nums[2] = 3. It is smaller than 9. Because the array is sorted, everything at or left of index 2 is smaller too, so none of it can be the target. Writing lo + (hi - lo) // 2 instead of (lo + hi) // 2 avoids integer overflow in C++ and Java.mid ± 1, not mid, matters: mid is already ruled out, and keeping it could loop forever.nums[2] = 3. It is larger than 2. Because the array is sorted, everything at or right of index 2 is larger too, so none of it can be the target. Writing lo + (hi - lo) // 2 instead of (lo + hi) // 2 avoids integer overflow in C++ and Java.mid ± 1, not mid, matters: mid is already ruled out, and keeping it could loop forever.nums[0] = -1. It is smaller than 2. Because the array is sorted, everything at or left of index 0 is smaller too, so none of it can be the target. Writing lo + (hi - lo) // 2 instead of (lo + hi) // 2 avoids integer overflow in C++ and Java.mid ± 1, not mid, matters: mid is already ruled out, and keeping it could loop forever.nums[1] = 0. It is smaller than 2. Because the array is sorted, everything at or left of index 1 is smaller too, so none of it can be the target. Writing lo + (hi - lo) // 2 instead of (lo + hi) // 2 avoids integer overflow in C++ and Java.lo <= hi. Once the pointers cross, every index has been ruled out, and the target is proven absent after only 3 comparisons.Recursive binary search
Each call searches the window [lo, hi], returns -1 once it is empty, and otherwise recurses into the one half that can still hold the target.
Common pitfalls
Using lo < hi with an inclusive hi
lo, hi = 0, len(nums) - 1 while lo < hi:
lo, hi = 0, len(nums) - 1 while lo <= hi:
When lo == hi one element is still unchecked. The strict condition exits first, so [5] with target 5 wrongly returns -1.
Not moving past mid
if nums[mid] < target:
lo = mid
else:
hi = midif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1mid is already ruled out. With lo = mid, a window of two elements can stop shrinking and the loop never ends.
Overflow in the midpoint
int mid = (lo + hi) / 2;
int mid = lo + (hi - lo) / 2;
For large arrays lo + hi can exceed INT_MAX and wrap negative, giving an invalid index. This exact bug sat in Java's own Arrays.binarySearch for years.
Edge cases
Index 0 and index n - 1 are reachable only if hi starts at n - 1 and the loop runs while lo <= hi. Test both ends: they catch off-by-one bugs that a target in the middle never exposes.
The window empties (lo > hi) and the loop exits. Return -1 after the loop, not from inside it.
Complexity
Binary search variants
The loop stays the same; what changes is what you do on a match and which bound you return.
| Problem | Question | On nums[mid] == target | Returns |
|---|---|---|---|
| Binary Search (704) | is the target present? | return mid | index or -1 |
| Search Insert Position (35) | first index with value >= target | hi = mid - 1, keep going | lo |
| First and Last Position (34) | leftmost and rightmost match | record mid, keep searching one side | two indices |
| Search in Rotated Array (33) | target in a rotated sorted array | return mid | check which half is sorted first |
| Koko Eating Bananas (875) | smallest speed that works | search over answers, not indices | lo |
Binary Search FAQ
What is binary search?
Binary search finds a value in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it. It runs in O(log n) time instead of the O(n) of a linear scan.
What are the steps?
- Precondition: the array is sorted in ascending order.
- Initialise:
lo = 0,hi = n - 1. - Loop: while
lo <= hi, setmid = lo + (hi - lo) / 2. - Compare: equal, return
mid;nums[mid] < target, setlo = mid + 1; else sethi = mid - 1. - End: return -1.
- Complexity: O(log n) time, O(1) space.
- Example:
[-1, 0, 3, 5, 9, 12], target 9: mid 2 (3 < 9), mid 4 (9 found), answer 4.
How fast is it?
O(log n). After k comparisons the window has at most n / 2^k elements, so it is empty after about log₂ n + 1 steps. Best case is O(1), when the first middle element is the target. Space is O(1) iteratively.
Why use lo + (hi - lo) / 2 instead of (lo + hi) / 2?
In languages with fixed-size integers, lo + hi can overflow for very large arrays and produce a negative index. lo + (hi - lo) / 2 gives the same middle without ever exceeding hi. In Python both are safe.