[Search][Rotate][Binary search] Search in Rotated Sorted Array ||

1. Example
Duplicate is allowed in Search in Rotated Sorted Array I duplicate is not allowed.
s=[4,5,6,7,0,1,2] and target is 7
Return true


2. Implementation
Thought1: linear O(n)

Thought2: Binary Search O(log(n))
but rotated, search the part is sorted
Q1: how to know which part is sorted ? rotated pivot?
A1: middle element compare to start and end
Q1: rotated?
A1: big part close to start and small part close to end, end value < start value
Q1: diff btw bs and roated?
A1: num[l] vs num[m] , care the part is sorted
//NOTE:

if (nums[l] < nums[m])
else if (nums[l] > nums[m]){
}
else { // duplicate l++; }

// Time:O(n), Space:O()
// Input:
//[1], 1
//Output:
//false
// Input:
//[1,3], 3
//Output:
//false
//Expected:
//true
//Input:
//[1,3,5], 1
//Output:
//false
//Expected:
///true
// Input:
//[3,5,1], 1
//Output:
//false
//Expected:
//true
// Input:
//[1,3], 3
//Output:
//false
//Expected:
//true
public boolean search(int[] nums, int target)
{

      // validate the input
      if ( nums == null || nums.length = 0)
      {
        return false;
      }
      



      int l = 0; 
      int r = nums.length-1;
      // NOTE: [1],1, so consider equal. The other reason is Big chance in the left-most or right-most
      while (l <= r)
      {
          int m = l + (r-l)>>1;
          if ( nums[m] == target )
          {
               return true;
          }




           


 if (nums[l] < nums[m])
 {
 // left part in order and target in range
 if ( target >= num[l] && target < nums[m] )
 {
 r = m-1
 }
 else 
 {
 l = m+1;
 }
 }
 else if ( nums[l] > nums[m] )
 {
 // right part in order and target among them
 if ( target > num[m] && target <= nums[r] )
 {
 l = m+1;
 }
 else 
 {
 r = m-1;
 }
 }
 else 
 { 
 // duplicate
 l++;
 }
 /*
 else if ( nums[m] > target )
 { 
 // NOTE: normally we just search left part means r = m-1 
 // case 4567 012 search 0 go right side 
 if ( nums[l] < nums[m] && nums[l] >= target ) 
 {
 r = m-1;
 }
 else 
 {
 l = m+1;
 }
 }
 else 
 { // case: 531 search 1/ go left side
 if ( nums[m] < nums[r] && nums[r] >= target)
 {
 l = m+1;
 }
 else 
 {
 r = m-1;
 }
 }
 */

}
    return false;
}

idx 0123   456
  s=4567   012
 
search 0
m = 3 s[m] =7 > 0
      s[m]=7 > s[0]=4

3. Similar Ones
(H) Search in Rotated Sorted Array
       Search insert position
       Search for a Range
       Search a 2D matrix
       Find minimum in Rotated Sorted Array I
       Find minimum in Rotated Sorted Array II