搜索旋转排序数组

题解思路

本题要求 $O(\log n)$ 的时间复杂度，因此我们必须使用 二分查找。

1. 旋转数组的特点

旋转数组由两个递增的子数组拼接而成，例如：

原数组:     [0, 1, 2, 4, 5, 6, 7]
旋转后:     [4, 5, 6, 7, 0, 1, 2]  （旋转点在 7 之后）

由于数组仍保持局部有序，我们可以通过二分查找找到 target。

2. 二分查找思路

在 nums[left] 到 nums[mid] 和 nums[mid] 到 nums[right] 之间 至少有一部分是有序的：

• 如果 nums[left] <= nums[mid]，说明 [left, mid] 这部分是有序的。
  • 若 target 在 [left, mid] 范围内，搜索左侧。
  • 否则搜索右侧。
• 否则 [mid, right] 是有序的：
  • 若 target 在 [mid, right] 范围内，搜索右侧。
  • 否则搜索左侧。

复杂度分析

• 时间复杂度：$O(\log n)$，二分查找的每次操作都将搜索区间缩小一半。
• 空间复杂度：$O(1)$，仅使用常数级别的额外空间。

代码实现

Python 代码

import sys

def search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        # 判断哪一部分是有序的
        if nums[left] <= nums[mid]:  # 左半部分有序
            if nums[left] <= target < nums[mid]:  # 目标值在左侧
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半部分有序
            if nums[mid] < target <= nums[right]:  # 目标值在右侧
                left = mid + 1
            else:
                right = mid - 1

    return -1

# 读取输入
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline().strip())

# 输出结果
print(search(nums, target))

Java 代码

import java.util.Scanner;

public class Main {
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            // 判断哪一部分是有序的
            if (nums[left] <= nums[mid]) {  // 左半部分有序
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {  // 右半部分有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        int target = scanner.nextInt();
        System.out.println(search(nums, target));
    }
}

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        // 判断哪一部分是有序的
        if (nums[left] <= nums[mid]) {  // 左半部分有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {  // 右半部分有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int target;
    cin >> target;

    cout << search(nums, target) << endl;
    return 0;
}

Leetcode 66.搜索旋转排序数组-原题链接

题目内容

整数数组 $nums$ 按升序排列，数组中的值互不相同 。

在传递给函数之前，$nums$ 在预先未知的某个下标 $k(0 <= k < nums.length)$上进行了旋转，使数组变为 $[nums[k], nums[k+1], ...,$$nums[n-1], nums[0], nums[1], ..., nums[k-1]]$ (下标 从 $0$ 开始 计数)。例如， $[0,1,2,4,5,6,7]$在下标 $3$ 处经旋转后可能变为 $[4,5,6,7,0,1,2]$。

给你旋转后的数组 $nums$ 和一个整数 $target$ ，如果 $nums$ 中存在这个目标值 $target$ ，则输出它的下标，否则返回 $-1$。

你必须设计一个时间复杂度为 $O(log\ n)$的算法解决此问题。

输入描述

• 第一行输入一个整数 n，表示数组的长度。
• 第二行输入 n 个整数，表示旋转后的数组 nums。
• 第三行输入一个整数 target，表示需要查找的目标值。

输出描述

• 输出一个整数，表示目标值 target 在数组中的索引，若不存在则输出 -1。

样例

样例 1

输入

7
4 5 6 7 0 1 2
0

输出

4

样例 2

输入

7
4 5 6 7 0 1 2
3

输出

-1

样例 3

输入

1
1
0

输出

-1

提示：

• $1 <= nums.length <= 5000$
• $-10^4 <= nums[i] <= 10^4$
• $nums$中的每个值都独一无二
• 题目数据保证 $nums$ 在预先未知的某个下标上进行了旋转
• $-10^4 <= target <= 10^4$