Search for a command to run...
Try your own input
Change the array and replay the algorithm from step one.
Current step
Plain binary search stops at any occurrence of 8. To find the first, keep searching left after a hit; to find the last, keep searching right. Two passes, each O(log n).
Two Binary Searches
1function firstOccurrence(nums, target) {2 let low = 0, high = nums.length - 1;3 let first = -1;4 5 while (low <= high) {6 const mid = low + Math.floor((high - low) / 2);7 8 // Hit — but keep looking left9 if (nums[mid] === target) {10 first = mid;11 high = mid - 1;12 }13 else if (nums[mid] < target) low = mid + 1;14 else high = mid - 1;15 }16 return first;17}18 19function lastOccurrence(nums, target) {20 let low = 0, high = nums.length - 1;21 let last = -1;22 23 while (low <= high) {24 const mid = low + Math.floor((high - low) / 2);//target: 8n: 6first: -1last: -125 26 // Hit — but keep looking right27 if (nums[mid] === target) {28 last = mid;29 low = mid + 1;30 }31 else if (nums[mid] < target) low = mid + 1;32 else high = mid - 1;33 }34 return last;35}36 37function searchRange(nums, target) {38 const first = firstOccurrence(nums, target);39 if (first === -1) return [-1, -1];40 const last = lastOccurrence(nums, target);41 return [first, last];42}