A: 35. Search Insert Position#
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Constraints:
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums contains distinct values sorted in ascending order
- -10^4 <= target <= 10^4
function searchInsert(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
if (target <= nums[0]) {
return left
}
if (target > nums[right]) {
return right + 1
}
let mid = Math.floor((left + right) / 2)
while (left < right - 1) {
const midValue = nums[mid]
if (midValue === target) {
return mid
}
if (midValue < target) {
left = mid
} else {
right = mid
}
mid = Math.floor((left + right) / 2)
}
return right
}
Submission Result:
65/65 cases passed (64 ms)
Your runtime beats 72.07 % of typescript submissions
Your memory usage beats 52.45 % of typescript submissions (43.7 MB)
Seeing that the problem requires an algorithm with O(logn) runtime complexity, it can be inferred that binary search is needed. I was able to start faster this time since I just did a binary search problem a few days ago. I spent some time thinking about the boundary conditions when writing. First, since mid is always a value between left and right, it cannot cover cases beyond this boundary. Therefore, I first checked if the target would exceed the maximum boundary, and returned the boundary condition if it did. Then, left and right will continue to shrink until left === right - 1, at which point the interval can no longer be compressed, so the loop should be terminated. Finally, because we have already determined in advance that the value will not exceed the range of left and right, if no item is hit during the process, the correct insertion position is simply right.