Search a sorted array by halving it
Say you have a sorted array of a million numbers and want to know whether 7,412 is one of them. Checking the numbers one by one from the left can take a million comparisons. Binary search finds a value in a sorted array by comparing it with the middle element, which rules out half of the array, and repeating the same step on the half that is left. For a million numbers it never has to look at more than 20 of them.
To see how one comparison can rule out half of an array, take six sorted values and look for 14:
position 0 1 2 3 4 5value 3 8 11 14 20 27Positions 0 to 5 have two middle positions, 2 and 3. Start at the lower one, position 2, which holds 11. That is less than 14. The array is sorted, so the values at positions 0 and 1 are smaller still, and none of the first three positions can hold 14. One comparison has ruled out all three, and 14 can only be at positions 3 to 5.
Now do the same with the positions that are left. The middle of 3 to 5 is position 4, which holds 20. That is more than 14, and every value after it is larger still, so positions 4 and 5 are out. Only position 3 remains, and it holds 14.
Each look at a middle value is called a probe. This search took three, at positions 2, 4 and 3.
A value that is missing shows up as a range with no positions left. Looking for 12 makes the same first two probes, because 12 is also more than 11 and less than 20. The third probe finds 14 at position 3, which is more than 12, so position 3 is ruled out as well. No position is left, which means 12 is not in the array.
On six values this saves little: a scan from the left finds 14 on its fourth comparison. The saving grows with the array, because every probe removes about half of whatever is left, however much that is.
The binary search loop
In code, the search keeps two variables, left and right: the first and the last position where the target could still be. At the start they are the two ends of the array, positions 0 and . As long as the range from left to right holds at least one position, the loop probes the middle one, mid, and compares its value with the target:
- If the value at
midequals the target, the search is over: the target is atmid. - If the value is less than the target,
midand every position before it are ruled out, soleftmoves tomid + 1. - If the value is greater than the target,
midand every position after it are ruled out, sorightmoves tomid - 1.
Every pass either ends the search or takes mid out of the range, so the range gets shorter each time and the loop has to end. The loop only removes positions whose values are too small or too large to be the target, so if left passes right and the range is empty, the target is not in the array.
LeetCode's Binary Search asks for this function:
You get a sorted array nums of distinct integers and a target. Return the target's position, or -1 if it is not in the array, in time.
Constraints
-
nums[i],target numsis sorted in ascending order and its values are distinct
Sample 1 · Input
nums = [-1,0,3,5,9,12], target = 9
Output
4
Sample 2 · Input
nums = [-1,0,3,5,9,12], target = 2
Output
-1
In the first sample, 9 is at position 4. In the second, 2 would have to sit between the values 0 and 3, and it is not there, so the answer is .
The listing writes the middle of the range as left plus half the distance from left to right, rounded down. That is the same position as the average of left and right, rounded down, and the Deeper read under the listing explains why this form is the safer habit.
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
nums = [-1, 0, 3, 5, 9, 12]
print(search(nums, 9), search(nums, 2))The program prints 4 and -1, the answers to the two samples.
How many probes can a search take? A probe leaves at most half of the positions that were in the range, because neither side of mid holds more than half of them. A million positions become at most 500,000 after one probe, 250,000 after two, and fewer than two after 19. So at most one position is left for the 20th probe, and a million values never take more than 20 probes:
In general, positions take at most probes, where is rounded down. The running time is , against for the scan, and doubling the array adds one probe.
Deeper read: the midpoint and integer overflow
The average, (left + right) / 2, and the form in the listing, left + (right - left) / 2, are the same position in exact arithmetic. They differ in languages whose integers have a fixed size. In C++ and Java, left + right is computed as an int first, and when both are above the sum is past the largest int, , and overflows. right - left is never larger than right, so the second form stays in range.
The binarySearch of the Java library used the plain average for about nine years before it broke a program, because the bug can only show on arrays of elements or more, about a billion.
Python integers do not overflow, so both forms are safe in Python. The listings use the second form anyway, so that the Python and C++ versions of a loop read the same.
Find the first value at least the target
The loop above answers one question, whether the target is in the array. For a missing target it returns , although the search has found out more than that. The search for 12 ruled out positions 0 to 2 because their values are too small, and positions 3 to 5 because their values are too large. So 12 belongs between position 2 and position 3, and inserting it at position 3 would keep the array sorted.
Many problems want that place. Search Insert Position asks for it directly:
You get a sorted array nums of distinct integers and a target. Return the target's position if it is in the array; otherwise return the position where it would go to keep the array sorted.
The solution must run in time.
Constraints
-
nums[i],target numsis sorted in ascending order and its values are distinct
Sample 1 · Input
nums = [1,3,5,6], target = 5
Output
2
Sample 2 · Input
nums = [1,3,5,6], target = 2
Output
1
Sample 3 · Input
nums = [1,3,5,6], target = 7
Output
4
In the three samples, 5 is at position 2, 2 belongs between 1 and 3 at position 1, and 7 is larger than every value, so it belongs after the end, at position 4. All three are answers to the same question: what is the first position whose value is at least the target? If no value is that large, as with 7, the answer is , the position just past the end. This position is called the lower bound of the target.
To find it, a probe no longer has three outcomes. It asks a yes-or-no question, "is the value at mid at least the target?", and acts on the answer:
- NO: the value is too small, and so is every value before it. As before,
leftmoves tomid + 1. - YES:
midcould be the answer, but an earlier position might also hold a value that is large enough. So the loop savesmidin a variableanswerand goes on searching the positions before it:rightmoves tomid - 1.
The loop never stops early now. It runs until the range is empty, and by then answer holds the first YES in the whole array. A NO throws away only positions whose values are too small, and a YES throws away only the positions after it, once it is saved. So the first YES stays in the range until a probe lands on it and saves it. Every later probe is to its left, where every answer is NO, so it stays in answer to the end.
The range changes too. The answer can be , so the search runs over positions 0 to , not 0 to . There is no value at position to compare, so the loop counts it as a YES without reading the array. It is the answer when every real value is too small.
The lower-bound loop
def search_insert(nums, target):
left, right, answer = 0, len(nums), 0
while left <= right:
mid = left + (right - left) // 2
if mid == len(nums) or nums[mid] >= target:
answer = mid
right = mid - 1
else:
left = mid + 1
return answer
nums = [1, 3, 5, 6]
print(search_insert(nums, 5), search_insert(nums, 2), search_insert(nums, 7))The program prints 2, 1 and 4, the answers to the three samples.
Compared with the first listing, the changes are the ones just described: the range ends at , position counts as a YES before the array is read, a YES is saved and the search goes on, and the function returns the saved answer. The value that answer starts with is never returned: position is a YES, so there is always a first YES for the loop to save.
Worked example
Trace the lower-bound loop
The trace runs this loop on the six values from the start of the page, with the target 12. Position is drawn at the end of the row. The range now has seven positions, 0 to , so the first probe is position 3, where the first loop started at position 2.
The other presets are the second sample of Search Insert Position, an array in which the target occurs twice, and a target larger than every value. With the repeated target, watch the search carry on to the left after it finds a 3: the first value at least 3 is the first copy of 3.
Optional practice. Try an answer or keep stepping; predictions do not award XP or solve credit.
Search for the first value at least target. Position n is a virtual YES, meaning every real value was too small.
- left
- 0
- right
- 6
- answer
- 0
Change the example input
Current result: 3
Monotone questions and the first YES
The lower-bound loop never used the values of the array directly. It only used the answers to "is this value at least the target?". For the six values and the target 12, those answers are:
position 0 1 2 3 4 5 nvalue 3 8 11 14 20 27at least 12? NO NO NO YES YES YES YESThe answers begin with NO, change to YES once, and never change back. The loop depends on that. After a NO at mid it throws away every position before mid, which is only safe if none of them can be a YES. After a YES it treats every position after mid as a YES too.
Definition
A yes-or-no question about a range of candidates is monotone if its answers, read in order, are all NO up to some point and all YES from there on. Either group can be empty.
Sorted order is what makes the question monotone here: if one value is at least the target, every value after it is at least as large. On an unsorted array the answers can go back to NO, and the loop returns wrong positions.
The loop itself has no need for an array. It needs a range of whole numbers, called the candidates, and a monotone question about them, and it returns the first candidate whose answer is YES. So the rest of this chapter calls it the first-YES loop. The candidates can be times or speeds as well as positions, and the loop is the same.
Loop invariant
Every candidate before left is a NO, and every candidate after right is a YES.
A statement that stays true through every pass of a loop is called a loop invariant. This one is true before the first probe, when no candidate is outside the range. left only moves to mid + 1 after a NO at mid, and because the question is monotone, every candidate before mid is a NO as well. right only moves to mid - 1 after a YES at mid, and every candidate after mid is a YES as well.
When the loop ends, left is one more than right: each pass moves left or right just past mid, which lies between them, so left can pass right by one and no further. By the invariant, every candidate before left is a NO and every candidate from left on is a YES. That makes left the first YES. It is the candidate that answer holds, so the loop can return left and do without answer.
If you are ever unsure whether an update in your own loop should be mid, mid + 1 or mid - 1, pick the one that keeps the invariant true and still takes mid out of the range, so that the loop ends.
How many probes a search takes
- Scan from the left
- Up to comparisons.
- Binary search for a value
time, extra space - At most probes: 10 for a thousand values, 20 for a million, 30 for a billion.
- Lower bound
time, extra space - At most probes, because the range has candidates.
On the later pages a probe does more work than one comparison. The cost is then the number of probes times the cost of one probe.
Common binary-search mistakes
Writing
while left < rightin the first loop.- Where it breaks
- On
[5]with target 5,leftandrightare both 0, so the loop body does not run and the search returns-1for a value that is in the array. - The fix
- Use
left <= right: a range of one position still has to be probed.
Setting
left = midafter a value that is too small.- Where it breaks
- On
[1, 5]with target 5,midis 0 and holds 1.left = midleaves the range at positions 0 to 1, the next probe is position 0 again, and the loop never ends. - The fix
midhas been checked, so leave it out of the range:left = mid + 1.
Running binary search on an array that is not sorted.
- Where it breaks
- On
[5, 1, 3]with target 5, the first probe finds 1 at position 1, which is too small, and discards position 0, where the 5 is. The search returns-1. - The fix
- Use binary search only when the input is guaranteed to be sorted. Sorting it yourself changes the positions, so that only helps when the question is whether the value is present.
Reading
nums[mid]in the lower-bound loop without testing for position .- Where it breaks
- Search Insert Position with
[1, 3, 5, 6]and target 7 probes positions 2, 3 and then 4, which is . Readingnums[4]raisesIndexErrorin Python and is undefined behavior in C++. - The fix
- Test whether
midequals before reading the array, as the listing does.
Recall Looking for 12 in `[3, 8, 11, 14, 20, 27]`, the lower-bound loop gets a YES on its first probe, at position 3, and position 3 turns out to be the answer. Why can the loop not return it straight away?
A YES only says that the value at mid is large enough. It does not say that mid is the first such position. Looking for 8 in the same array, the first probe is also position 3 and also a YES, but the answer is position 1. The loop can only tell the two cases apart by searching the positions before mid, so it saves the YES and carries on.
Recall A sorted array has 1,000 values. What is the largest number of probes the first loop can need to find a value or report that it is missing?
Ten. The range goes from 1,000 positions to at most 500, 250, 125, 62, 31, 15, 7, 3 and 1, which is nine probes, and the tenth probe looks at the last position. The formula gives the same: .
Key terms
| Term | Meaning |
|---|---|
| probe | One look at the middle of the range. |
| lower bound | The first position whose value is at least the target, or if there is none. |
| candidate | One of the whole numbers the loop searches over: a position here, an answer on later pages. |
| monotone | A yes-or-no question whose answers are all NO up to some candidate and all YES from there on. |
| first-YES loop | The lower-bound loop, used with any monotone question. |