Binary Search
Binary Search: given a sorted array of distinct integers and a target, return its index or -1 if it is absent, running in O(log n) time.
- 1 <= nums.length <= 10⁴
- -10⁴ < nums[i], target < 10⁴
- All integers in nums are unique
- nums is sorted in ascending order
Intuition
Sortedness means one comparison rules out half the array: if the middle element is too small, every element to its left is too small as well. Repeatedly halving a range of n elements reaches a single candidate in about log₂ n steps, which is why an array of a million entries is decided in twenty comparisons. The discipline is entirely in the bookkeeping — which half survives, and when the search space is empty.
Binary search applies whenever the search space is ordered and a single test tells you which side the answer is on. That test does not have to be an array lookup — it can be any monotone predicate, which is what turns capacity and rate questions into searches over the answer rather than the input.
Approach
Before reading on: decide whether your interval is inclusive or half-open, then make the loop condition and the bound updates agree with that choice. Test your version on a single-element array — that is where the <= versus < mistake shows up first.
Why one comparison eliminates half
Take the middle index mid. If nums[mid] == target the search is over. If nums[mid] < target, sortedness guarantees every index at or below mid also holds a value below the target, so the entire left half plus mid can be discarded in one move. The mirror argument discards the right half when nums[mid] > target. Nothing here depends on the values themselves, only on the ordering — which is exactly why the array must be sorted for the method to be valid at all.
The closed interval and its exit condition
This version keeps lo = 0 and hi = len(nums) - 1, both inclusive, so the invariant reads if the target exists it lies in [lo, hi]. The loop condition must therefore be while lo <= hi, because lo == hi still describes one unexamined element. Dropping to < would skip that final candidate and report a miss on single-element ranges. When lo passes hi the interval is genuinely empty, every element has been ruled out, and -1 is the honest answer.
Computing the midpoint without overflow
(lo + hi) // 2 is safe in Python, whose integers grow without bound, but in C++ and Java the sum can exceed the 32-bit range when both bounds are large and silently wrap negative — a bug that sat in the JDK's own binary search for nearly a decade. Writing lo + (hi - lo) / 2 computes the same midpoint while keeping every intermediate value within the existing range. The two forms are mathematically identical; only one is safe in fixed-width arithmetic.
Solution & live demo
Common pitfalls
Using while 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 candidate is still unexamined. The strict condition exits before checking it, so a single-element array, or a target that narrows down to one index, wrongly returns -1.
Failing to exclude mid when narrowing
if nums[mid] < target:
lo = mid
else:
hi = midif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1mid has already been compared and ruled out. Leaving it inside the range means a two-element interval can stop shrinking, and the loop spins forever.
Overflow in the midpoint on fixed-width integers
int mid = (lo + hi) / 2;
int mid = lo + (hi - lo) / 2;
In C++ and Java, lo + hi can exceed INT_MAX for large arrays and wrap to a negative value, producing an out-of-bounds index. The subtraction form never leaves the existing range.
Edge cases
The interval empties, lo passes hi, and -1 is returned.
The range narrows leftward until lo == hi == 0.
The inclusive hi makes the final index reachable.
lo == hi == 0, so the <= condition runs the one needed comparison.
Every probe moves the same bound until the interval collapses.