搜索旋转排序数组 II

题目

题目来源：力扣（LeetCode）

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

思路分析

由题意可知，一个按非降序排列（即升序排序）的数组，旋转之后，会变成较大的值在前面，较小的值在后面

旋转之后的数组，存在两种情况：
(1)两头的值等于目标值，那么我们就从后往前找小于目标值的位置，从前往后找大于目标值的位置，如果两头的值等于目标值, 证明数组中存在待查找目标值，直接返回true;
(2)如果两头的值不等于目标值，分成两层关系；如果 mid <= tail，证明当前中间的位置mid在后半段递增关系 中，所以当前确定关系区间是mid - tail；如果 mid > tail，证明当前中间位置mid在前半段递增关系中，所以 当前确定关系区间是head - mid。

// 使用二分查找，怎么分是关键，举个例子：
// 第一类
// 1011110111 和 1110111101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
// 第二类
// 22 33 44 55 66 77 11 这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；
// 这种情况下，前半部分有序。因此如果 nums[start] <= target < nums[mid]，则在前半部分找，否则去后半部分找。
// 第三类
// 66 77 11 22 33 44 55 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；
// 这种情况下，后半部分有序。因此如果 nums[mid] < target <= nums[end]。则在后半部分找，否则去前半部分找。
var search = function (nums, target) {
    // 首先确定两头的值等不等于target,存在返回true
    if (nums[0] == target || nums[nums.length - 1] == target) return true;
    // 如果不等于的话，就把两头相等的值给他去掉,设置左右区间
    let mid, l = 0, r = nums.length - 1, head, tail;
    // 因为去掉两头相等的值，保证待查找区间的头的值大于尾部的值，二分到中间值的时候 方便做判断
    while (l < nums.length && nums[l] == nums[0]) ++l;
    while (r >= 0 && nums[r] == nums[0]) --r;
    head = l, tail = r;
    while (l <= r) {//证明当前待查找区间还有数
        mid = (l + r) >> 1;
        if (nums[mid] == target) return true;//首先第一层判断，中间值在前半段有序区间还是在后半段的有序区间中
        if (nums[mid] <= nums[tail]) {//在后半段的有序区间中
            // target 在后半部分
            if (target > nums[mid] && target <= nums[tail]) l = mid + 1;
            // 否则，去前半部分找
            else r = mid - 1;
        } else {//在前半段的有序区间中
            // target 在前半部分
            if (target < nums[mid] && target >= nums[head]) r = mid - 1;
            // 否则，去后半部分找 
            else l = mid + 1;
        }
    }
    return false;
};