😟33 search in rotated sorted array

https://leetcode.com/problems/search-in-rotated-sorted-array/

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        int len = nums.length;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }
        if (nums[left] == target) {
            return left;
        } else if (nums[right] == target) {
            return right;
        }
        return -1;
    }
}

原理所有人都懂但是很难搞对 array被分成了两个上升区间，主要分为两种情况，left和mid在同一个上升区间，和left在左边大的区间而mid在右边小的区间，

在第一种情况中又有两个情况，第一种是target比mid小，且target和left以及mid在同一区间，第二种是初次之外的情况，如target比mid大，此时如果target比left大就还是在同一区间，如果反倒比left小就无解了，无论如何都可以直接移动right

在第二种情况中也有两种情况，第一种是target比mid大但是比right小，这说明target也在第二个较小的上升区间，跟mid一样，第二种是target比mid小，如果target比right小，则可能有解，如果target反而比right大，就一定无解了，无论如何都可以直接移动right

总之记住两种大情况，left和mid在不在同一区间，以及各自两种子情况，target和mid在不在同一区间

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while (left+1 < right) {
            int mid = (left+right)/2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                if (nums[mid] > nums[right]) {
                    if (target > nums[right]) {
                        right = mid;
                    } else {
                        // different segment
                        left = mid;
                    }
                } else {
                    right = mid;
                }
            } else {
                if (nums[mid] < nums[left]) {
                    if (target < nums[left]) {
                        left = mid;
                    } else {
                        // different segment
                        right = mid;
                    }
                } else {
                    left = mid;
                }
            }
        }
        if (nums[left] == target) {
            return left;
        }
        if (nums[right] == target) {
            return right;
        }
        return -1;
    }
}

其实只需要记住两种特殊情况 midVal < target时如果midVal在右段target在左段（通过和leftVal比较得知），和midVal > target时如果midVal在左段但是target在右段（通过和rightVal比较得知），这两种情况很明显移动方向时反的，其余情况跟普通binary search没有区别