15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Binary search finds a target in a sorted array by halving the candidate range. It compares the middle element with the target, discards the half that cannot hold it along with the middle, and repeats. It runs in O(log n) time and O(1) extra space, and it only works if the array is sorted.
| Worst case time | O(log n), the range halves each step |
|---|---|
| Best case time | O(1), the first midpoint matches |
| Extra space | O(1) for the iterative version |
| Requires | Array sorted in nondecreasing order |
| Midpoint | low + (high - low) // 2 |
| Loop condition | while low <= high, bounds inclusive |
Binary search assumes you already know linear search: inspect candidates until you find the target or run out of candidates.
Binary search requires a sorted array:
A must be sorted in nondecreasing order.The lesson uses inclusive boundaries:
low is the first candidate index.high is the last candidate index.[low, high].When low > high, that interval is empty. No candidate indices remain.
The algorithm returns:
i such that A[i] == target, if it finds one;-1, if the target is absent.The implementation structure and binary-search definition here follow the scope of the supplied references: Algorithms, 4th edition companion site and the data structures and algorithms course outline.
Use this sorted array:
1A = [1, 4, 6, 9, 12]
2target = 9Show both indices and values:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Value | 1 | 4 | 6 | 9 | 12 |
At the beginning, every index could contain 9.
1low = 0
2high = 4
3
4candidate interval = [0, 4]The midpoint is:
1mid = low + (high - low) // 2
2 = 0 + (4 - 0) // 2
3 = 2Index 2 contains 6.
Since 6 < 9, the target cannot be at index 2 or anywhere to its left:
1indices 0 through 2 contain [1, 4, 6]Because the array is sorted, all of those values are at most 6. None can equal 9.
So the next candidate interval is [3, 4].
Start with the full array as the candidate interval.
Binary search for 9 in [1, 4, 6, 9, 12]: mid = 2 holds 6 < 9, so low becomes 3; then mid = 3 holds 9, a match, so return 3.
1low = 0
2high = 4
3mid = 0 + (4 - 0) // 2 = 2
4A[mid] = A[2] = 6The comparison is:
1A[mid] < target
26 < 9The sorted order gives this fact:
1A[0], A[1], and A[2] are all less than or equal to 6.They cannot equal 9. Discard indices 0, 1, and 2.
Change only low:
1low = mid + 1 = 3
2high = 4The new candidate interval is [3, 4].
1low = 3
2high = 4
3mid = 3 + (4 - 3) // 2 = 3
4A[mid] = A[3] = 9The comparison is:
1A[mid] == target
29 == 9The target is found.
1return 3The ordered states are:
| State | low | high | mid | A[mid] | Result |
|---|---|---|---|---|---|
| 0 | 0 | 4 | 2 | 6 | Discard indices 0 through 2; next interval is [3, 4] |
| 1 | 3 | 4 | 3 | 9 | Target found |
| 2 | — | — | — | — | Return index 3 |
Before the first comparison, every array index was still possible. After seeing A[2] = 6, indices 0 through 2 were no longer possible, but indices 3 and 4 still were.
The statement that remains true is:
At the start of every iteration, if the target occurs in the sorted array, at least one occurrence lies within the inclusive interval
[low, high].
The statement is the loop invariant.
It does not say every value in the interval matches the target. It says that binary search never discards all possible locations of the target.
For the example:
9 occurs at index 3, which is inside [0, 4].0 through 2, index 3 is still inside [3, 4].3, so the algorithm finds the target.Start with all valid indices:
1low = 0
2high = length(A) - 1As long as low <= high, there is at least one candidate index.
Choose a midpoint without forming low + high directly:
1mid = low + (high - low) // 2Now compare A[mid] with target.
A[mid] == targetThe midpoint is a valid answer.
1return midA[mid] < targetEvery index from low through mid contains a value no greater than A[mid].
Since A[mid] < target, none of those indices can contain the target.
Discard them:
1low = mid + 1The + 1 matters. Index mid was checked and cannot be the answer.
A[mid] > targetEvery index from mid through high contains a value no smaller than A[mid].
Since A[mid] > target, none of those indices can contain the target.
Discard them:
1high = mid - 1Again, the - 1 matters because index mid was checked.
If repeated discards make low > high, no candidate index remains. Return -1.
Function contract
1binarySearch(A, target) -> integer
2
3Inputs:
4 A: a nondecreasing array of integers
5 target: an integer to search for
6
7Returns:
8 Any index i such that A[i] == target, if one exists.
9 Otherwise, -1.
10
11Mutation behavior:
12 Does not modify A.
13
14Boundaries:
15 low and high are inclusive.
16 An empty array begins with low = 0 and high = -1.11 function binarySearch(A, target) -> integer
22 low <- 0
33 high <- length(A) - 1
44
55 while low <= high
66 mid <- low + (high - low) // 2
77
88 if A[mid] == target
99 return mid
1010
1111 if A[mid] < target
1212 low <- mid + 1
1313 else
1414 high <- mid - 1
1515
1616 return -1The midpoint expression on line 6 keeps the difference high - low separate before adding it to low.
Dry-run the exact pseudocode with:
1A = [1, 4, 6, 9, 12]
2target = 9| Line | Action | low | high | mid | Result |
|---|---|---|---|---|---|
| 2 | Set low <- 0 | 0 | — | — | First array index |
| 3 | Set high <- length(A) - 1 | 0 | 4 | — | Last array index |
| 5 | Test low <= high | 0 | 4 | — | 0 <= 4, so enter loop |
| 6 | Set mid <- 0 + (4 - 0) // 2 | 0 | 4 | 2 | Midpoint is index 2 |
| 8 | Test A[2] == 9 | 0 | 4 | 2 | 6 == 9 is false |
| 11 | Test A[2] < 9 | 0 | 4 | 2 | 6 < 9 is true |
| 12 | Set low <- mid + 1 | 3 | 4 | 2 | Discard indices 0 through 2 |
| 5 | Test low <= high | 3 | 4 | 2 | 3 <= 4, so enter loop |
| 6 | Set mid <- 3 + (4 - 3) // 2 | 3 | 4 | 3 | Midpoint is index 3 |
| 8 | Test A[3] == 9 | 3 | 4 | 3 | 9 == 9 is true |
| 9 | Return mid | 3 | 4 | 3 | Return 3 |
The returned index is 3, and A[3] is 9.
We prove that binarySearch returns an index containing target when one exists, and returns -1 when it does not.
Before the loop:
1low = 0
2high = length(A) - 1The interval contains every valid array index.
Therefore, if target occurs anywhere in A, at least one occurrence lies in [low, high]. The invariant holds before the first iteration.
For an empty array, high = -1. The interval [0, -1] is empty, and the loop does not run.
For the empty-interval state shown by A = [2, 5] with target = 3, low = 1 and high = 0. Because low > high, no index lies in the candidate interval, so the result is -1.
Assume the invariant holds at the start of an iteration.
The algorithm chooses mid in [low, high].
There are three comparison outcomes.
A[mid] == target
The algorithm returns mid. Since A[mid] equals the target, this return value is correct.
A[mid] < target
Since A is nondecreasing, every index i with low <= i <= mid satisfies:
1A[i] <= A[mid] < targetSo no index from low through mid can contain the target.
Updating:
1low = mid + 1removes only impossible candidate indices. If the target occurs, an occurrence remains in the new interval [low, high]. The invariant is preserved.
A[mid] > target
Since A is nondecreasing, every index i with mid <= i <= high satisfies:
1A[i] >= A[mid] > targetSo no index from mid through high can contain the target.
Updating:
1high = mid - 1removes only impossible candidate indices. If the target occurs, an occurrence remains in the new interval [low, high]. The invariant is preserved.
On every nonmatching comparison:
low = mid + 1 removes mid and all earlier candidates, orhigh = mid - 1 removes mid and all later candidates.So the number of candidate indices strictly decreases.
Eventually, either:
low > high.When low > high, the candidate interval is empty. By the invariant, if the target occurred in the array, at least one occurrence would have to lie in that interval. No such index exists, so the target is absent. Returning -1 is correct.
Let m be the number of indices in the current candidate interval.
At the start, there are at most n candidates.
Each loop iteration does a constant amount of work:
A[mid];On a nonmatching comparison, binary search keeps at most about half of the candidates:
1m becomes at most ceil(m / 2)After k iterations, the remaining interval has size at most about:
1n / 2^kThe interval becomes empty once repeated halving reduces its size below one candidate. Repeated halving reaches that point when k is proportional to:
1log2(n)Therefore, the worst-case running time is:
1O(log n)A successful search may finish earlier. In the example, it takes two iterations. The worst case includes searches where the target is absent and searches that reach the last remaining candidate.
The iterative algorithm stores only:
1low, high, mid, target, and a constant number of temporary valuesIt does not allocate another array or use recursive calls.
Its auxiliary space is:
1O(1)Incorrect assumption: Binary search works on any array.
Exposing input:
1A = [3, 1, 2]
2target = 1The first midpoint is index 1, where A[1] = 1, so this particular arrangement happens to succeed. Midpoint-based discarding has no general justification when order is missing. A different target or discard can eliminate an index that contains the answer.
For example, if a comparison sees a midpoint value smaller than the target, binary search discards the left half only because sortedness guarantees all values there are no greater than that midpoint. An unsorted array provides no such guarantee.
Correction: Require a nondecreasing sorted array. If the input is not sorted, use linear search instead.
low = mid instead of low = mid + 1Incorrect line:
1if A[mid] < target
2 low <- midExposing input:
1A = [1, 3]
2target = 3Initial state:
1low = 0
2high = 1
3mid = 0
4A[mid] = 1Since 1 < 3, the incorrect update sets:
1low = mid = 0The state remains:
1low = 0
2high = 1
3mid = 0The next iteration repeats forever.
Correction:
1low <- mid + 1The update removes the checked midpoint from the candidate interval.
low < high with inclusive boundariesIncorrect loop condition:
1while low < highExposing input:
1A = [1, 3]
2target = 3Initial state:
1low = 0
2high = 1
3mid = 0
4A[mid] = 1Since 1 < 3, update:
1low = mid + 1 = 1Now:
1low = 1
2high = 1There is still one candidate: index 1. But low < high is false, so the loop stops without inspecting A[1].
The wrong output is:
1-1Correction:
1while low <= highWith inclusive bounds, low == high represents a valid singleton candidate interval.
| Input | Expected result |
|---|---|
A = [], target = 4 | -1, without calculating a valid midpoint |
A = [8], target = 8 | 0 |
A = [8], target = 7 | -1 |
A = [1, 3, 5, 7], target = 1 | 0 |
A = [1, 3, 5, 7], target = 7 | 3 |
A = [1, 3, 5, 7], target = 4 | -1 |
Implement:
1binarySearch(A, target)Contract to satisfy:
A is a nondecreasing integer array.i where A[i] == target.-1 when target is absent.A.low and high boundaries.Tests verify:
1def binary_search(a, target):
2 low, high = 0, len(a) - 1
3 while low <= high:
4 mid = low + (high - low) // 2 # never forms low + high
5 if a[mid] == target:
6 return mid
7 if a[mid] < target:
8 low = mid + 1 # mid was checked, drop it
9 else:
10 high = mid - 1
11 return -1
12
13print(binary_search([1, 4, 6, 9, 12], 9))
14print(binary_search([1, 4, 6, 9, 12], 5))1public class Main {
2 static int binarySearch(int[] a, int target) {
3 int low = 0, high = a.length - 1;
4 while (low <= high) {
5 int mid = low + (high - low) / 2; // never forms low + high
6 if (a[mid] == target) return mid;
7 if (a[mid] < target) low = mid + 1; // mid was checked, drop it
8 else high = mid - 1;
9 }
10 return -1;
11 }
12
13 public static void main(String[] args) {
14 int[] a = {1, 4, 6, 9, 12};
15 System.out.println(binarySearch(a, 9));
16 System.out.println(binarySearch(a, 5));
17 }
18}1#include <iostream>
2#include <vector>
3using namespace std;
4
5int binarySearch(const vector<int>& a, int target) {
6 int low = 0, high = (int)a.size() - 1;
7 while (low <= high) {
8 int mid = low + (high - low) / 2; // never forms low + high
9 if (a[mid] == target) return mid;
10 if (a[mid] < target) low = mid + 1; // mid was checked, drop it
11 else high = mid - 1;
12 }
13 return -1;
14}
15
16int main() {
17 vector<int> a = {1, 4, 6, 9, 12};
18 cout << binarySearch(a, 9) << endl;
19 cout << binarySearch(a, 5) << endl;
20}1function binarySearch(a, target) {
2 let low = 0, high = a.length - 1;
3 while (low <= high) {
4 const mid = low + Math.floor((high - low) / 2); // never forms low + high
5 if (a[mid] === target) return mid;
6 if (a[mid] < target) low = mid + 1; // mid was checked, drop it
7 else high = mid - 1;
8 }
9 return -1;
10}
11
12const a = [1, 4, 6, 9, 12];
13console.log(binarySearch(a, 9));
14console.log(binarySearch(a, 5));On sorted data, yes: O(log n) comparisons against O(n). On unsorted data, binary search can discard the half that holds the target, so linear search is the right tool. Sorting first costs more than one linear scan, so a single lookup in unsorted data is cheaper with linear search.
Use it when the data is sorted and you look values up, or when a yes-or-no question flips once along an ordered range. The second case is binary search on the answer.
It needs sorted input and constant-time access to the middle element, which an array gives you. It also returns any matching index, not necessarily the first one, so duplicates need the lower-bound variant.
It avoids forming low + high directly, which can overflow in fixed-width integer types. Adding half the difference to low gives the same midpoint.
Index mid was already checked, so it must leave the interval. With A = [1, 3] and target 3, low = mid keeps low at 0 and the loop never ends.