Search Insert Position
EasyLower bound: first index ≥ target
Find the spot where a number belongs so the list stays sorted, by halving the search each step.
The idea
This is a lower-bound search: find the leftmost position where the target could be inserted to keep the array sorted. Binary search narrows to that boundary.
1
3
5
6
0
1
2
3
x5
Step 1 of 5. Brute force: scan left to right for the first value at least 5. Values: 1, 3, 5, 6. x 5.
1/5
Brute force
timeO(n)spaceO(1)
Scan for the spot.
1let ans = n;2for (let i = 0; i < n && ans === n; i++)3 if (nums[i] >= target) ans = i;4return ans;Input
- array
- [1, 3, 5, 6]
Memory
- i
- —
- x
- 5
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 3, 5, 6], target = 5
- Output:
- 2
- Explanation:
- 5 is already at index 2.
Example 2
- Input:
- nums = [1, 3, 5, 6], target = 2
- Output:
- 1
- Explanation:
- 2 would slot in at index 1.
Example 3
- Input:
- nums = [1, 3, 5, 6], target = 7
- Output:
- 4
- Explanation:
- 7 belongs at the end, index 4.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.