34. Search for a Range Leetcode Java

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Solution:

Modified Binary search

1. Find the leftmost index with value= target: if A[m]>=target, update res and r=m-1;

2. Find the rightmost index with value=target: if A[m]<=target update res and l=m+1;

Time complexity O(logn) do binary search twice.

 public int[] searchRange(int[] A, int target) {  
     int[] res={-1,-1};  
     if(A==null || A.length==0) return res;  
     int l=0;  
     int r=A.length-1;  
     while(l<=r){  
       int m=(r-l)/2+l;  
       if(A[m]==target){  
         if(res[0]==-1) {  
           res[0]=m;  
           res[1]=m;  
         }  
         else res[0]=m;  
         r=m-1;  
       }  
       else if(A[m]>target) r=m-1;  
       else l=m+1;  
     }  
     if(res[0]==-1) return res;  
     l=res[1]+1;  
     r=A.length-1;  
     while(l<=r){  
       int m=(r-l)/2+l;  
       if(A[m]==target){  
        res[1]=m;  
         l=m+1;  
       }  
       else if(A[m]>target) r=m-1;  
       else l=m+1;  
     }  
     return res;  
   }