Search Insert Position
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
