LeetCode 81. 搜索旋转排序数组 II

小灰灰 2022-11-07 13:29 165阅读 0赞

# 81. 搜索旋转排序数组 II #

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 \[0,0,1,2,2,5,6\] 可能变为 \[2,5,6,0,0,1,2\] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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

进阶:

*  这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
 *  这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

## 题解 ##

本题是需要使用二分查找，怎么分是关键，举个例子：

*  第一类  
    10111和 11101这种。此种情况下 `nums[start] == nums[mid]`，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
 *  第二类  
    2 3 4 5 6 7 1 这种，也就是 `nums[start] < nums[mid]`。此例子中就是 2 < 5；  
    这种情况下，前半部分有序。因此如果`nums[start] <=target<nums[mid]`，则在前半部分找，否则去后半部分找。
 *  第三类  
    6 7 1 2 3 4 5 这种，也就是 `nums[start] > nums[mid]`。此例子中就是 6 > 2；  
    这种情况下，后半部分有序。因此如果 `nums[mid] <target<=nums[end]`。则在后半部分找，否则去前半部分找。

转载于：[https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan/][https_leetcode-cn.com_problems_search-in-rotated-sorted-array-ii_solution_zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan]

## 代码 ##

class Solution { 
    public:
        bool search(vector<int>& nums, int target) { 
            int start=0,end=nums.size()-1;
            while(start<=end)
            { 
                int mid=(end+start)/2;
                
                if(nums[mid]==target)
                    return true;
                if(nums[mid]==nums[start])
                { 
                    start++;
                }
                // 右边已经排好序
                else if(nums[mid] > nums[start])
                { 
                    if(target <nums[mid] && target >= nums[start])
                        end = mid - 1;
                    else 
                        start=mid+1;
                }
                else   // 左边已经排好序
                { 
                    if(target>nums[mid] && target <= nums[end])
                        start=mid+1;
                    else
                        end=mid-1;
                }
              
            }
            return false;
        }
    };

[https_leetcode-cn.com_problems_search-in-rotated-sorted-array-ii_solution_zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan/