【二分】(中等)Leetcode 33. 搜索旋转排序数组

最新推荐文章于 2025-01-15 12:00:00 发布

Bryce1010_贤哉回也

最新推荐文章于 2025-01-15 12:00:00 发布

阅读量286

点赞数

分类专栏： 1.4 ACM之路之精选技巧

本文链接：https://blog.csdn.net/Fire_to_cheat_/article/details/104196694

版权

1.4 ACM之路之精选技巧专栏收录该内容

4 篇文章

订阅专栏

本文介绍了一种在O(logn)时间复杂度下解决旋转升序数组中查找目标元素的问题，利用二分搜索原理，通过判断当前查询位置属于哪一段升序数组，从而将问题转化为常规的二分搜索。

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

在这里插入图片描述
[题目]

题目大意如上所属，要求在O(logn)的时间复杂度解决。
要求时间复杂度为O(logn)，首先要想到直接要循环搜索出旋转位置的方法是O(n)以上，所以不可行；
那么根据题目中升序排序数组关键词容易想到，二分搜索来解决。
通过分析可以发现，旋转后的数组由前一段升序和后一段升序组成。那么可以在每次查询过程中，判断当前查询位置是属于前一段还是后一段，这样就转化成常规的二分。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l,r,mid;
        int len=nums.size();
        l=0,r=len-1;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(nums[mid]==target)
                return mid;
            if(nums[mid]>=nums[l])//左侧
            {
                if(nums[mid]>=target&&target>=nums[l])
                    r=mid-1;
                else
                    l=mid+1;
            }
            else if(nums[mid]<=nums[r])//右侧
            {
                if(nums[mid]<=target&&target<=nums[r])
                    l=mid+1;
                else
                    r=mid-1;
            }
        }
        return -1;

    }
};