Given a sorted array of distinct integers 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.
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
Example 4:
Input: nums = [1,3,5,6], target = 0 Output: 0
Example 5:
Input: nums = [1], target = 0 Output: 0
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 104numscontains distinct values sorted in ascending order.-104 <= target <= 104
Idea:
Use Binary Search
- Time complexity: O(logn)
- Space complexity: O(1)
Solution:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let l = 0;
let r = nums.length;
while (l < r) {
let mid = l + Math.floor((r - l) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};