leetcode81. Search in Rotated Sorted Array-CSDN博客

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/60776894

本文介绍了一种在旋转排序数组中查找特定元素的方法。该数组原本按升序排列，但已知在其某处进行了未知的旋转。文章提供了两种解决方案：一种适用于无重复元素的情况，另一种则考虑了数组中可能存在重复元素的情形。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

medium题

题目:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

大意是一个无重复元素的递增数组，以某个元素为轴翻转过去了，比如1,2,3,4,5,6,7 以5为轴翻转为6,7,1,2,3,4,5

在这个数组中查找给定元素。

可以用二分法来解

AC解

class Solution 
{
public:
    bool search(vector<int>& nums, int target) 
    {
        int first = 0,v_size = nums.size();
        int last = v_size;
        if (last == 0)
            return false;
            
        while (first < last)
        {
            int middle = first + (last - first) / 2;
            
            if (nums[middle] == target)
                return true;
            
            if (nums[first] <= nums[middle])
            {//说明first到middle是递增的
                if (target >= nums[first]&&target < nums[middle])
                    last = middle;
                else first = middle + 1;
            }
            else 
            {
                if (target > nums[middle]&&target <= nums[last - 1])
                    first = middle + 1;//middle到last-1是递增的
                else last = middle;
            }
        }
        
        return false;
    }
};

升级版，允许有重复元素

则nums[first] <= nums[middle]不能说明first到middle是递增的，如1,3,1,1

需要细分

AC解

class Solution 
{
public:
    bool search(vector<int>& nums, int target) 
    {
        int first = 0,v_size = nums.size();
        int last = v_size;
        if (last == 0)
            return false;
            
        while (first < last)
        {
            int middle = first + (last - first) / 2;
            
            if (nums[middle] == target)
                return true;
            
            if (nums[first] < nums[middle])
            {
                if (target >= nums[first]&&target < nums[middle])
                    last = middle;
                else first = middle + 1;
            }
            else if (nums[first] > nums[middle])
            {
                if (target > nums[middle]&&target <= nums[last - 1])
                    first = middle + 1;
                else last = middle;
            }
            else first++;
        }
        
        return false;
    }
};