搜索旋转排序数组
    image.png
    完全有序查找可以使用二分
    这种部分有序也可以找到二分的点来缩减搜索半径。
    只是这种二分策略能不能描述地清晰优雅。
    step1 ： 通过例子发现，[4,5,6,7,0,1,2] 不管切分点在哪，至少一半是有序的
    step2 ：因为题干说元素不重复，所以判断有序的一半数据，方式比较简单，就看尾部元素是否大于最前面元素就可以了。
    step3： 如果要搜索的target在有序区间取值中，就在区间中搜索，否则在另一半搜索
    step4: 注意base case要考虑，如果搜索不到，返回-1；

    上面通过在有序区间中搜索的逻辑比我这个判断mid ，left， target三者的关系，堆叠的if-else要优雅的多。

    1. public static void main(String[] args) {
    2.         int[] arr = {1,3};
    3.         int res = process(arr ,0, 0 ,arr.length-1);
    4.         System.out.println(res);
    6.     }
    7.     public static int process(int[] nums, int target, int l, int r) {
    8.         if(l > r) return -1;
    9.         if(l == r){
    10.             return  nums[l] == target? l : -1;
    11.         }
    12.         if(nums[l] == target ) return l;
    13.         if(nums[r] == target) return r;
    14.         int mid = l + ((r-l)>>1);
    15.         int res = -1;
    16.         if(nums[mid] == target) return mid;
    17.         if(nums[mid] > target){
    18.             if(nums[mid] >nums[l]){
    19.                 if(nums[l]< target) {
    20.                     res = process(nums, target, l, mid - 1);
    21.                 }
    22.                 else {
    23.                     res = process(nums, target, mid+1, r);
    24.                 }
    25.             }else {
    26.                 if(nums[l]<target){
    27.                     res= process(nums, target, mid+1, r);
    28.                 }
    29.                 else {
    30.                     res = process(nums, target,l, mid-1);
    31.                 }
    32.             }
    34.         }
    35.         else if(nums[mid] < target){
    36.             if(nums[mid]>nums[l]){
    37.                 if(nums[l] < target){
    38.                     res = process(nums, target, mid+1, r);
    39.                 }
    40.             }else {
    41.                if(nums[l]> target){
    42.                    res = process(nums, target,mid+1, r);
    43.                }else {
    44.                    res = process(nums, target, l, mid-1);
    45.                }
    46.             }
    47.         }
    48.         return res;
    49.     }

    下面是官方的
    image.png
    image.png
    tips：

    • 优雅的找二分条件，可以节省很多if-else。这里采用有序区间法。
    • 一半题解习惯用循环实现二分逻辑，我习惯用递归来实现二分。 ```java class Solution { public int search(int[] nums, int target) {
      1.   int n = nums.length;
      2.   if (n == 0) {
      3.       return -1;
      4.   }
      5.   if (n == 1) {
      6.       return nums[0] == target ? 0 : -1;
      7.   }
      8.   int l = 0, r = n - 1;
      9.   while (l <= r) {
      10.       int mid = (l + r) / 2;
      11.       if (nums[mid] == target) {
      12.           return mid;
      13.       }
      14.       if (nums[0] <= nums[mid]) {
      15.           if (nums[0] <= target && target < nums[mid]) {
      16.               r = mid - 1;
      17.           } else {
      18.               l = mid + 1;
      19.           }
      20.       } else {
      21.           if (nums[mid] < target && target <= nums[n - 1]) {
      22.               l = mid + 1;
      23.           } else {
      24.               r = mid - 1;
      25.           }
      26.       }
      27.   }
      28.   return -1;
      }

    作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 ```