
Sponsored
Sponsored
The goal is to use the binary search algorithm to achieve O(log n) time complexity. We perform two separate binary searches:
Time Complexity: O(log n) due to binary search. Space Complexity: O(1) as no extra space is used apart from input and output.
1var searchRange = function(nums, target) {
2 const findFirst = (nums, target) => {
3 let left = 0, right = nums.length - 1, result = -1;
4 while (left <= right) {
5 const mid = left + Math.floor((right - left) / 2);
6 if (nums[mid] >= target) {
7 if (nums[mid] === target) result = mid;
8 right = mid - 1;
9 } else {
10 left = mid + 1;
11 }
12 }
13 return result;
14 };
15
16 const findLast = (nums, target) => {
17 let left = 0, right = nums.length - 1, result = -1;
18 while (left <= right) {
19 const mid = left + Math.floor((right - left) / 2);
20 if (nums[mid] <= target) {
21 if (nums[mid] === target) result = mid;
22 left = mid + 1;
23 } else {
24 right = mid - 1;
25 }
26 }
27 return result;
28 };
29
30 return [findFirst(nums, target), findLast(nums, target)];
31};The JavaScript solution is similar to the other languages, implementing two helper functions for binary searching the first and last instance of the target value.