[Search][Binary Search] Search for a range

1. Example
idx 0 1 2 3 4  5
s= [5,7,7,8,8,10] and target value is 8
return [3,4]


2. Implementation
Complexity Time:O(log(n)) Space:O(1)
BS to search for a target value
Q1: how to know it is left bound or right bound
A1: since it is sorted, we can iterating right or left until non-target value is hit. More Specifically,

For the left bound, we use this formula
num[m] < target , l = m+1
num[m] >= target, r = m-1
When value equal happen, we keep decreasing the right bound until nums[m] < target happen.
When num[m] < target happen, l == r and m = (r+l)>>1 = l = r, so we take l = m+1 and while loop stop since l > r(m+1 > m) and l is our left bound

For the right bound, we use  the formula
num[m] > target, r = m-1
num[m] <= target, l=m+1
When value equal happen, we keep increasing the left bound until num[m] > target happen.
When num[m] > target happen, l==r and m = (r+l)>>1 = l=r, so we take r = m-1 and while loop stop
since l > r(m > m-1) and r is our right bound

Note: left bound and right bound. manipulate BS
if ( nums[m] >= target ) { r = m-1; } else { l_leftbound =m+1; }

if ( nums[m] <= target ) { l = m+1; } else { r_rightbound= m-1; }

// Time:O(log(n)) ,Space:O(1)
public int[] searchRange (int[] nums, int target)
{


     int[] res = new int[2];
     res[0] =-1;
     res[1] =-1;
     // validate the input 
     if ( nums == null || nums.length == 0)
     {
         return res;
     }




     int l_leftbound = 0;
     int r = nums.length -1;
     //int foundIndex = -1;
     while( l <= r )
     { 
          int m = (l+r) >>1;
          //if ( nums[m] == target )
          //{
          //    foundIndex = m;
          //}
          //else if (  nums[m] > target )
          if (  nums[m] >= target ) 
          {
              r = m-1;
          } 
          else 
          {
              l_leftbound =m+1;
          }
     }
     

     

     int l = 0; 
     int r_rightbound = nums.length -1;
     while (  l<=r )
     {
         int m = (1+r) >> 1;
         if ( nums[m] <= target )
         {   
            l = m+1;
         }
         else 
         { 
           r_rightbound = m-1;
         }
     }

  

    
     if (l_leftbound <= r_rightbound )
     {
          res[0] = l_leftbound;
          res[1] = r_rightbound;
     }
     return res;


}

3. Similar Ones
(M)  Search Insert Position