搜索旋转排序数组

题意

给定旋转一次的升序无重复数组，查找 target 的下标，不存在返回 -1。要求 $O(\log n)$ 。

思路

虽然数组整体无序，但二分后必有一半是有序的。判断方法：若 nums[l] <= nums[mid]，左半有序；否则右半有序。

确定有序半区后，判断 target 是否落在该半区的值域内：

左半有序且 nums[l] <= target < nums[mid]：r = mid - 1，搜索左半。
左半有序但 target 不在左半：l = mid + 1，搜索右半。
右半有序且 nums[mid] < target <= nums[r]：l = mid + 1，搜索右半。
右半有序但 target 不在右半：r = mid - 1，搜索左半。

每轮排除一半，保证 $O(\log n)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().search(a, t) << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            if nums[l] <= nums[m]:
                if nums[l] <= target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -1


def main():
    n, t = map(int, input().split())
    a = list(map(int, input().split()))
    print(Solution().search(a, t))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(\log n)$ 。
空间复杂度： $O(1)$ 。

总结

旋转数组二分的核心观察：二分后必有一半有序。先判断哪半有序，再判断 target 是否在该半区，从而缩小范围。nums[l] <= nums[mid] 的等号处理了 l == mid 的情况。

搜索旋转排序数组

目录

题意

思路

代码

复杂度

总结