力扣经典面试题——搜索旋转排序数组及最小值（二分搜索旋转数组系列一次搞定）

我们先来看看一个常规的二分搜索是如何进行的？
例如要找一个有序数组的某个数
【1，2，4，5，9，11，15，19】
我们要找11，每次我们分割半边判断然后看到底在哪一边。
这里为什么我们可以直接砍掉半边？因为数组有序，如果要找的数比mid大，那么一定不在左半边。
带着上面的这种思想，进入正题：
先来看这个搜索旋转排序数组：https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked
我们发现，这个数组分割为了两个有序的数组。这个就会让我们想到两次二分。即找到那个第一次下降的点，然后左边二分右边二分。但是如果要找到这个点我们一定要遍历整个数组，时间复杂度O(n)，虽然能过这题，但是这个和题目要求的Logn复杂度差得远。
既然复杂度只能是logn说明了什么？说明我们一定可以直接通过二分得到答案。
好，我们来看如何一步步推出结论。首先我们先尝试着二分看看，如果我们二分，就会出现这种情况，就是二分得到的点，左边右边并不是严格递增，如果一个数小于mid那么可能会导致他不在mid前面而是在mid后面。这样我们砍不掉半边。但是我们这个时候观察到，左右半边一定会有一个半边递增，那么我们可以局部判断，就看哪里递增，我们只需要判断目标在不在那个有序的半边，不在就二分另外半边，怎么判断哪个半边有序，直接首尾看看递不递增就行了。
故得到思路：由于这个是一个旋转数组，所以如果找到一个分割点一定可以保证一个半边是有序的，然后根据这个有序的半边可以判断target在不在这个半边，如果在那么就递归这个半边，不然就另外半个。

class Solution {
    public int search(int[] nums, int target) {
        //思路：由于这个是一个旋转数组，所以如果找到一个分割点
        //一定可以保证一个半边是有序的，然后根据这个有序的半边可以判断
        //target在不在这个半边，如果在那么就递归这个半边，不然就另外半个
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(target==nums[mid])return mid;
            //后面半边是否有序，即找到有序的半边进
            if(nums[mid]<=nums[right]){
                //看target在不在这个半边
                if(nums[mid]<=target&&target<=nums[right]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }else{
                if(nums[left]<=target&&target<=nums[mid]){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
        }
        return -1;
    }
}

再来看另外一个，寻找旋转排序数组中的最小值。https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-100-liked
这次我们要找的其实就是那个旋转的起始点，也就是整个数组的最小值。思路类似，由于旋转的点一定在不递增的半边，所以根据这个特征二分就行了，还有一个点就是如果都递增怎么办？思考过后再看后面的答案。
核心思路：找非递增的半边，如果都递增那么就找小的半边。

class Solution {
    public int findMin(int[] nums) {
        //找非递增的半边，如果都递增那么就找小的半边
        int left = 0;
        int right = nums.length-1;
        while(left<right){
            int mid = (left+right)/2;
            //有不递增的一边
            if(nums[mid]<nums[left]||nums[mid]>nums[right]){
                if(nums[mid]<nums[left]){
                    right = mid;
                }else{
                    left = mid+1;
                }
            }
            //两边都递增
            else{
                right = mid;
            }
        }
        return nums[left];
    }
}