LeetCode33.搜索旋转排序数组

更新: 2/4/2026 字数: 0 字 时长: 0 分钟

题目链接：LeetCode33.搜索旋转排序数组

根据题目我们可以简单的发现，给定的数组可以分成两段不同的有序的数组，思路也是进行二分查找，只是查找时会出现一点区别。

我们以$[4,5,6,7,0,1,2]$为例，我们可以发现我们任意选取一个位置将他切成两段，一定有一段是有序的，另一段可能不有序，我们分情况讨论：

1. 如果这段是有序的，那么我们就可以正常二分，就是如果target在这个有序区间内，我们就将区间缩小到这一个范围，不在就取另一段。
2. 如果这段是无序的，那么另一段一定是有序的，同上进行处理。

故我们只要处理好这个范围的判定和估计，就能解决掉这道题了。参考代码如下：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0,r = n - 1;
        if(n == 1) {
            if(nums[0] == target) return 0;
            else return -1;
        }
        while(l <= r) {
            int mid = (l + r) / 2;
            if(nums[mid] == target) return mid;
            // 这里是判断是否左边区间是有序的
            if(nums[mid] >= nums[l]) {
                // 如果target在[nums[l],nums[mid]]范围内，就在这区间内查找，否则就查找另一边
                if(nums[mid] > target && nums[l] <= target) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                // 这里就是左边不有序，所以右边就有序，同上进行处理
                if(nums[mid] < target && nums[r] >= target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

一开始我在14行这里判断时我写的是>，导致[3,1] 1这组数据会被hack掉，就是因为在相同情况下他就只有一个数，那么也是有序的。