Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
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
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