【Hot100】33. 搜索旋转排序数组

33. 搜索旋转排序数组
中等题
但凡是从有序序列中找某个数，第一反应 应该是「二分」。
一个原本有序的数组在某个点上进行了旋转，其实就是将原本一段升序的数组分为了两段。
「二分」的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」。
经过旋转的数组，显然前半段满足 >= nums[0]，而后半段不满足 >= nums[0]。我们可以以此作为依据，通过「二分」找到旋转点。

class Solution {
    
    public int search(int[] nums, int target) {
    
        //数组长度
        int n = nums.length;
        //数组中无元素
        if (n == 0) {
    
            return -1;
        }
        //数组中有一个元素
        if (n == 1) {
    
            return nums[0] == target ? 0 : -1;
        }
        //定义二分查找的左右边界
        int l = 0, r = n - 1;
        while (l <= r) {
    
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
    
                return mid;
            }

            if (nums[0] <= nums[mid]) {
    
                //如果target在[l,mid]内一直缩小右边界
                if (nums[0] <= target && target < nums[mid]) {
    
                    r = mid - 1;
                } else {
     // target<nums[0] ,target>nums[mid] 不在[l,mid]区间内，往右找
                    l = mid + 1;
                }
            } else {
     //nums[0] > nums[mid] [5,6,0,1,2,3,4]
                if (nums[mid] < target && target <= nums[n - 1]) {
    
                    l = mid + 1;
                } else {
    
                    r = mid - 1;
                }
            }
        }
        return -1;

    }
}