public class Solution {
    public int search(int[] A, int target) {
      int len = A.length;
          
          // binary search
          int l = 0;
          int r = len -1;
          
          while(l <= r){
              int m = (l+r)/2;
              if(target == A[m]){
                  return m;
              }
              
              if(A[m] >= A[l]){ // lower is sorted ** do not forget "="
                  if(target >= A[l] && target < A[m]){  // 注意这边的等号 左边要包含等号
                      r = m-1;
                  }else{
                      l = m+1;
                  }
              } else { // higher is sorted
                  if(target > A[m] && target <= A[r]){ // 注意这边的等号 右边要包含等号
                      l = m+1;
                  }else {
                      r = m-1;
                  }
              }
          }
          return -1;
    }
}