Search insert position
EasyStuck?
Show a hintHide the hint
Halve the range each step. When the loop ends without finding it, the low end is where it belongs.
The idea behind this problem
Next in this lesson
Where a repeated value starts and endsGiven a sorted array of distinct integers and a target, return the index where the target is found. If it is not present, return the index where it would be inserted to keep the array sorted.
Your solution must run in logarithmic time.
Constraints#
1 <= n <= 200000- The array is sorted in increasing order.
Input
nums is a count then that many sorted integers. target is one integer.
Output
A single index, zero-based.
Examples
Input
4 1 3 5 6 5
Output
2
5 is already present at index 2.
Input
4 1 3 5 6 2
Output
1
2 would sit between 1 and 3, so it belongs at index 1.
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.