Problem
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Example 3:
Input: nums = [], target = 0 Output: [-1,-1] Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109numsis a non-decreasing array.-109 <= target <= 109
Solution
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange = function(nums, target) { var index = findIndex(nums, target); return index === -1 ? [-1, -1] : [findLeft(nums, target, index), findRight(nums, target, index)]; }; var findIndex = function(nums, target) { var left = 0; var right = nums.length - 1; while (left <= right) { var mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return -1; }; var findLeft = function(nums, target, index) { var left = 0; var right = index; while (left < right) { var mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) { right = mid; } else { left = mid + 1; } } return left; }; var findRight = function(nums, target, index) { var left = index; var right = nums.length - 1; while (left < right) { var mid = left + Math.ceil((right - left) / 2); if (nums[mid] === target) { left = mid; } else { right = mid - 1; } } return right; }; Explain:
nope.
Complexity:
- Time complexity : O(log(n)).
- Space complexity : O(1).