Search in Rotated Sorted Array

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

A[mid] >= A[left] 说明 mid 左边已经排序好了；

else 右边已经排序好了

然后 根据 A[mid] 和 target的大小比较 二分搜索

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;
    }
}