Back to course home
0% completed
Vote For New Content
Attempt.
Shane
Jul 10, 2023
my approach. when mid is found use two pointers to check either side of mid.
function find_range(arr, key) { let left=0, right=arr.length-1 while(left <= right){ let mid = (left+right) >>> 1 if(arr[mid] < key) left = mid + 1 else if(arr[mid] > key) right = mid - 1 else{ let lft = mid, rgt = mid while(lft >= 0 && arr[lft-1] == arr[mid]) lft-- while(rgt <= arr.length-1 && arr[rgt+1] == arr[mid]) rgt++ return [lft,rgt] } } return [-1,-1]; }
0
0
Comments
Comments
wuchuan 2 years ago
I had this approach as well but realised that in the worst case, the numbers in the array can all be equals to key. Which would mean that the left and right expansion will take O(N) time.
On this page