Find it by halving
EasyStuck?
Show a hintHide the hint
Track a low and high bound. Compare the middle against the target and move whichever bound the comparison rules out.
The ideas behind this problem
Next in this lesson
Search insert positionGiven a sorted list of distinct numbers and a target, return the position of the target, or -1 if it is not there.
Worked example#
For [-1, 0, 3, 5, 9, 12] and target 9, look at the middle and throw away the half that cannot contain it:
| low | high | middle | value there | what it tells you |
|---|---|---|---|---|
| 0 | 5 | 2 | 3 | 3 is less than 9, so the answer is to the right |
| 3 | 5 | 4 | 9 | found it, position 4 |
Two comparisons instead of five.
For target 2 in the same list:
| low | high | middle | value there | what it tells you |
|---|---|---|---|---|
| 0 | 5 | 2 | 3 | too big, look left |
| 0 | 1 | 0 | -1 | too small, look right |
| 1 | 1 | 1 | 0 | too small, look right |
| 2 | 1 | low passed high, so it is not here |
Return -1.
Why it is fast#
Each step throws away half of what is left. A list of a million values is down to one in about 20 steps, because doubling 20 times passes a million. That is what O(log n) means, and it is only possible because the list is sorted: order is what lets you discard a half without looking at it.
Compute the middle as low + (high - low) / 2, not (low + high) / 2. In a language with fixed width integers the second can overflow when both are large, which is a bug that lived in the Java standard library for nine years.
Constraints#
1 <= n <= 100000- The values are sorted in increasing order and all distinct
-1000000 <= nums[i], target <= 1000000
Input
nums is a count then that many integers, sorted. Then target is one integer.
Output
The position of the target, or -1.
Examples
Input
6 -1 0 3 5 9 12 9
Output
4
9 sits at position 4.
Input
6 -1 0 3 5 9 12 2
Output
-1
2 is not in the list at all.
Input
1 5 5
Output
0
A single value that matches is at position 0.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.