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

男娘i 2022-05-08 05:44 294阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/description/][https_leetcode-cn.com_problems_search-in-rotated-sorted-array-ii_description]

#### 题目描述 ####

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

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

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

#### 示例 ####

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

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

**进阶**:

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

#### 解决方法 ####

在[33. 搜索旋转排序数组][33.]的基础上,判断 right 和 mid 的值相等的情况

class Solution { 
    public:
        bool search(vector<int>& nums, int target) { 
            // 在33. 搜索旋转排序数组的基础上,判断right和mid的值相等的情况 
            
            int left=0,right=nums.size()-1;
            while(left<=right){ 
                int mid=(left+right)>>1;
                if (nums[mid]==target) return true;
                
                else if (nums[mid]<nums[right]){ 
                    if (nums[mid]<target && target<=nums[right]) left=mid+1;
                    else right=mid-1;
                }
                else if (nums[mid]>nums[right]){ 
                    if (nums[left]<=target && target<nums[mid]) right=mid-1;
                    else left=mid+1;
                }
                else
                    right--;
            }
            
            return false;
        }
    };

[https_leetcode-cn.com_problems_search-in-rotated-sorted-array-ii_description]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/description/
[33.]: https://blog.csdn.net/fuqiuai/article/details/82982846