Search Insert Position
Easy· binary search· lower bound
Problem
Given a sorted array of distinct integers and a target, return the index of the target if found. If it is missing, return the index where it would have to be inserted to keep the array sorted. Aim for O(log n).
Examples
Input: nums = [2,4,7,10], target = 7
Output: 2
Input: nums = [2,4,7,10], target = 5
Output: 2
5 belongs between 4 and 7, which is index 2.
Constraints
- • 1 <= nums.length <= 10^4
- • nums has distinct values sorted ascending
- • -10^4 <= target <= 10^4
Hints & approach
Hint 1
The answer is the first index whose value is greater than or equal to the target.
Hint 2
This is a lower-bound search; the answer can be nums.length.
Approachtry the hints first
Search for the lower bound: the first position whose value is at least the target. Use a half-open window lo = 0, hi = n. While lo < hi, if nums[mid] < target the answer lies strictly right of mid, so lo = mid + 1; otherwise mid itself could be the answer, so hi = mid. When the loop ends lo is both the match index (if present) and the insertion point (if not).
Time O(log n) · Space O(1)