【leetcode】在旋转排序数组中查找（二分）

最新推荐文章于 2025-03-11 16:53:58 发布

matrix6666

最新推荐文章于 2025-03-11 16:53:58 发布

阅读量471

点赞数

分类专栏： leetcode c++练习

本文链接：https://blog.csdn.net/matrix6666/article/details/78112255

版权

leetcode 同时被 2 个专栏收录

18 篇文章

订阅专栏

c++练习

14 篇文章

订阅专栏

本文介绍了一个LeetCode上的经典算法问题——在旋转过的有序数组中使用二分查找法寻找目标值。文章详细解释了如何根据数组的特性判断目标值可能存在的递增区间，从而有效地缩小搜索范围。

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

33. Search in Rotated Sorted Array

leetcode题目描述

题目描述：

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.

题解：

二分查找
已排序的数组以某一点为转轴旋转，转轴未知，找到target在数组中的位置。
每次分两种情况，即分界点在中线左边还是右边，并对这两种情况再具体处理。
用first和last来不断缩小查找范围，最后逼近实际位置。
考虑数值范围明显可知的区间，即确定哪部分递增
如果前/后半部分递增，情况有两种：
1. target在递增区间
2. target不在此递增区间
由此可确定target具体范围

solution1:

class Solution {
public:
    int search(const vector<int>& nums, int target) {
        int first = 0;
        int last = nums.size();
        while (first != last) {
            int mid = (first + last) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[first] <= nums[mid]) { // 前半部分递增 
                if (nums[first] <= target && target < nums[mid]) { // target在递增部分（可直接确定范围） 
                    last = mid;
                } else {
                    first = mid + 1;
                }
            } else { // 后半部分递增 
                if (nums[mid] < target && target <= nums[last-1]) {
                    first = mid + 1;
                } else {
                    last = mid;
                }
            }
        }
        return -1;
    }
};