[LC-81][chapter4][Binary Search] Search in Rotated Sorted Array II 在旋转数组中查找数字

Tag：二分法中文链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/

题目描述： 已知存在一个按非降序排列的整数数组 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 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 题目数据保证 nums 在预先未知的某个下标上进行了旋转 -10^4 <= target <= 10^4 进阶： 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

题目解读： 此题乍一看是在排好序的数组中寻找target，可以用双指针也可以用二分法查找。但是这题又不是一个单纯的排好序数组，数组nums在预先未知的某个下标进行了旋转，所以数组变成两组非降序排列的数组；接下来是尝试将问题简化为在单纯非降序排列的数组中查找数字。

数组两侧的下标分别用l，r表示，用二分法寻找数组的mid，会出现以下情况： 1，右侧是非降序数组，则nums[mid] <= nums[r] && nums[l]>=nums[mid]； 2，左侧是非降序数组，则nums[l] <= nums[mid] && nums[mid]>=nums[r]；注意到如果除去nums[l]=nums[mid]，这两种情况可以互为反情况。

先处理特殊情况，nums[l]=nums[mid]，需要先移动一个值来排除干扰，左端点向右移动一位后继续查找；再来处理两种情况，情况1，如果target在右侧区间里，则在右侧继续二分查找，否则在左侧查找；另一种情况则换成左侧操作。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        // 数组只有一个值，直接比较
        if(nums.size() == 1){
            return nums[0] == target;
        }

        int l = 0, r = nums.size() - 1;
        int mid;
        while(l <= r){
            mid = (l + r) / 2;
            // target = nums[mid]
            if(nums[mid] == target) return true;

            if(nums[l] == nums[mid]){
                ++ l;
            }else if(nums[mid] <= nums[r]){ // 情况1
                if(target > nums[mid] && target <= nums[r]){
                    l = mid + 1; // 右侧查找
                }else{
                    r = mid - 1;
                }
            }else{ // 情况2
                if(target < nums[mid] && target >= nums[l]){
                    r = mid - 1; // 左侧查找
                }else{
                    l = mid + 1;
                }
            }
        }
        return false;
    }
};

复杂度分析： 时间复杂度：二分法查找的复杂度是O(logn)，但是如果遇到元素重复的数组，需要遍历数组，则复杂度为O(n)，这点正如进阶中提到的，和搜索旋转排序数组问题的区别；空间复杂度：O(1)，额外使用的空间为常数。

renchord / SEU_MIMO_LeetCode

[LC-81][chapter4][Binary Search] Search in Rotated Sorted Array II 在旋转数组中查找数字 #19