60. Search Insert Position — Lower Bound
Find where the target belongs if it is inserted before existing equal values. Return the first index whose value is greater than or equal to the target, or the array length if there is none.
This is a boundary search, not merely a search for one equal value. The answer may point between existing values or just after the final position.
Example 1
Input
[1,2,2,4], target=2
Output
1
Explanation: Equality at mid=2 keeps right=2, then equality at index 1 keeps right=1; the earlier boundary is found.
Example 2
Input
[1,2,4], target=5
Output
3
Explanation: The insertion boundary after the array is valid but must not be indexed.
Example 3
Input
[], target=9
Output
0
Explanation: There is one empty-array insertion boundary.
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 1-231 <= target <= 231 - 1- nums is sorted in nondecreasing order; duplicates are allowed.
Hints
Hint 1
Think of each index as answering whether its value is at least target.
Hint 2
The true region starts somewhere between zero and n, inclusive.
Hint 3
Move left past too-small midpoints; keep an eligible midpoint by setting right=mid.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Equality moves toward the first duplicate
[1,2,2,4]
2
1