How binary search works
Binary search finds a value in a sorted array by halving the search range at every step. Compare the target with the middle element. If the middle is smaller, the target can only be in the right half; if it is bigger, only in the left half. Every comparison throws away half of what is left.
It is the number-guessing game. Someone picks a number from 1 to 100 and answers "higher" or "lower". Guess 50, then 75 or 25, and so on. You never need more than 7 guesses, because 2⁷ = 128 is more than 100.
The code keeps two indices, lo and hi: the inclusive ends of the range that could still hold the target. The loop runs while lo <= hi. When lo passes hi, the range is empty, so the target is not in the array and the function returns -1.
The number worth remembering: an array of n elements needs at most ⌊log₂ n⌋ + 1 probes. For 1,000,000 elements that is 20 probes, against up to 1,000,000 checks for a linear scan.
The algorithm in 5 steps
- 1 Set
lo = 0andhi = n − 1. - 2 While
lo <= hi, takemidhalfway between them, rounded down. - 3 If
a[mid]is the target, returnmid. - 4 If
a[mid]is smaller, setlo = mid + 1; otherwise sethi = mid − 1. - 5 If the loop ends, the target is not there: return -1.
Worked example
Here is every step of one search on a fixed array, generated by the same code as the visualizer.
Input: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target23
- Step 1 Look for 23 in indices 0–9. lo = 0, hi = 9. 25812162338567291
- Step 2 The middle of 0–9 is index 4 (halfway, rounded down). 25812162338567291
- Step 3 a[4] is 16, not 23. 25812162338567291
- Step 4 16 < 23, so 23 can only be to the right. Drop indices 0–4. 25812162338567291
- Step 5 lo = 5. Keep searching indices 5–9. 25812162338567291
- Step 6 The middle of 5–9 is index 7 (halfway, rounded down). 25812162338567291
- Step 7 a[7] is 56, not 23. 25812162338567291
- Step 8 56 > 23, so 23 can only be to the left. Drop indices 7–9. 25812162338567291
- Step 9 hi = 6. Keep searching indices 5–6. 25812162338567291
- Step 10 The middle of 5–6 is index 5 (halfway, rounded down). 25812162338567291
- Step 11 a[5] is 23. That is the target. 25812162338567291
- Step 12 Found 23 at index 5. 25812162338567291
Result: index 5, after 3 probes and 5 comparisons. Searching the same array for 24 takes 4 probes and returns -1.
Time and space complexity
Best
O(1)The target happens to be the first middle element.
Average
O(log n)Each probe halves the range, so most searches take close to log₂ n probes.
Worst
O(log n)At most ⌊log₂ n⌋ + 1 probes, including when the target is missing.
Space
O(1)The loop only keeps lo, hi and mid. A recursive version uses O(log n) stack.
- Needs sorted input:
- Yes
- Bounds:
- Inclusive
- Returns:
- Index or -1
- Duplicates:
- Any match
The visualizer's array has 12 numbers, so no search on it can take more than 4 probes. Double the array and the limit grows by just one probe.
When to use it, and when not to
Good fit
- Looking up values in a sorted array that changes rarely, such as a price list or a sorted ID table.
- Finding boundaries: the first value ≥ x (lower bound) or the first value > x (upper bound), for range counts and insert positions.
- "Binary search on the answer": when a yes/no check is monotonic, such as "can we ship everything in D days with capacity C?", search for the smallest C that works.
- Debugging: git bisect is binary search over commits, finding the one that introduced a bug in about log₂ n test runs.
Pick something else when
- The data is unsorted. Sorting first costs O(n log n), which only pays off if you will search many times.
- The data changes often. Inserting into a sorted array is O(n); a balanced search tree keeps both lookups and inserts at O(log n).
- You only need "is it there?". A hash set answers that in O(1) on average, with no sorting.
Common mistakes and bugs
-
1.while lo < hi with inclusive bounds
With
hi = n − 1, the loop must run whilelo <= hi. Stopping atlo < hiskips the last remaining candidate, so a target sitting at that index is reported as missing. -
2.Setting lo = mid or hi = mid
When
loandhiare neighbours,midequalslo, solo = midnever moves and the loop spins forever. With inclusive bounds, always move past mid:mid + 1ormid − 1. -
3.(lo + hi) / 2 overflowing
In Java, C and C++,
lo + hican exceed the integer range on very large arrays and go negative. Writelo + (hi − lo) / 2. Joshua Bloch reported in 2006 that this bug sat in Java's own Arrays.binarySearch for about nine years. Python integers do not overflow. -
4.Searching unsorted input
Binary search does not check that its input is sorted. On unsorted data it silently returns -1 for values that are there, or finds the wrong one. Sort first, or keep the data sorted on insert.
-
5.Expecting the first match among duplicates
The standard version returns whichever matching index it lands on first. If you need the first occurrence, use the lower-bound variant: on a match, record it and keep searching left.
Interview questions
Try answering before you open the model answer.
Q1 Find the first and last position of a target in a sorted array with duplicates.
Model answer: Run two boundary searches. The first finds the smallest index with a[i] >= target; the second finds the smallest index with a[i] > target, and the last position is that index minus one. If the first index is out of range or does not hold the target, return [-1, -1]. Both are O(log n).
Q2 Search for a target in a rotated sorted array.
Model answer: At any mid, at least one half is sorted. Check which half is sorted by comparing a[lo] with a[mid], then check whether the target lies inside that sorted half's range. If it does, search there; otherwise search the other half. This is O(log n) when values are distinct.
Q3 Why write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2?
Model answer: In languages with fixed-size integers, lo + hi can overflow when both are large, producing a negative mid and an out-of-bounds read. lo + (hi - lo) / 2 computes the same value without overflow. In Python it does not matter, but interviewers like to hear that you know why.
Q4 Compute the integer square root of n without a library.
Model answer: Binary search on the answer. Search m in [0, n] for the largest m with m × m <= n. If mid × mid <= n, record mid and go right; otherwise go left. That takes O(log n) steps.
Q5 Find the minimum ship capacity to deliver all packages within D days.
Model answer: Binary search on the capacity, between the heaviest package and the sum of all weights. For a candidate capacity, simulate greedily in O(n) to count the days needed. Feasibility is monotonic, so find the smallest capacity that fits in D days: O(n log(sum of weights)).
Frequently asked questions
Does binary search work on unsorted arrays?
No. It assumes that everything left of the middle is smaller and everything right is bigger. On unsorted data that assumption is false, so it can miss values that are present or return a wrong index, without any error. Sort the array first, or use a linear search or a hash set.
What is the time complexity of binary search?
O(log n) in the average and worst case, and O(1) in the best case, when the first middle element is the target. Each probe halves the remaining range, so an array of n elements needs at most ⌊log₂ n⌋ + 1 probes. The iterative version uses O(1) extra space.
Which index does binary search return when there are duplicates?
The standard version, shown here, returns whichever matching index it reaches first, which may not be the first occurrence. Java's Arrays.binarySearch documents the same: no guarantee which match is found. For the first occurrence, use a lower-bound search, such as Python's bisect_left, and check the value.
Should I write binary search recursively or iteratively?
Iteratively, in most cases. The loop version uses O(1) extra space, avoids recursion limits and is just as short. The recursive version is fine for explaining the idea, and the recursion depth is only about log₂ n, but it adds function-call overhead without making the code any clearer.
Is there a built-in binary search in Python, Java and JavaScript?
Python has the bisect module (bisect_left and bisect_right) for lower and upper bounds. Java has Arrays.binarySearch and Collections.binarySearch. JavaScript has no built-in binary search for arrays, so you write your own, like the version on this page, or use a library.