在排序旋转数组中查找目标值

1. 概述

在本文中，我们将探讨如何在一个排序且旋转的数组中查找特定目标值。这类问题在算法面试中较为常见，尤其是在考察对二分查找的理解和变种应用能力时。

我们会先定义问题并给出示例，接着提出一种高效的解决方案，最后分析其时间复杂度和实现细节。

2. 问题定义

给定一个整数 X 和一个**由不同整数组成的排序并旋转后的数组 A**，我们的任务是找出 A 中等于 X 的元素的索引位置。如果找不到该元素，则返回 -1。

⚠️ 假设数组中没有重复元素，这样问题更简洁，便于分析。

示例

考虑如下排序旋转数组：

RotatedArray

数组内容为：[7, 8, 9, 1, 2, 3, 4, 5, 6]

我们查找以下目标值：

X = 7 → 位置 0
X = 2 → 不存在，返回 -1
X = 1 → 位置 3

3. 二分查找法

3.1 核心思想

✅ 核心思路是利用二分查找算法，但与常规的二分查找不同，我们需要处理数组的旋转特性。

在每次二分过程中，我们比较中间元素 A[middle] 和目标值 X，并根据当前子数组的有序性决定向左还是向右查找。

三种情况分析：

A[middle] == X → 找到目标，直接返回 middle
**A[middle] < X**：
- 如果 A[low] > A[middle] 且 A[low] <= X：说明目标在左半边
- 否则：目标在右半边
**A[middle] > X**：
- 如果 A[high] < A[middle] 且 A[high] >= X：说明目标在右半边
- 否则：目标在左半边

通过这种方式，我们可以在每次迭代中排除一半的搜索空间，从而实现高效的查找。

3.2 算法实现（Java）

public class RotatedArraySearch {
    public static int search(int[] A, int X) {
        int low = 0;
        int high = A.length - 1;

        while (low <= high) {
            int middle = (low + high) / 2;

            if (A[middle] == X) {
                return middle;
            } else if (A[middle] < X) {
                if (A[low] > A[middle] && A[low] <= X) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            } else {
                if (A[high] < A[middle] && A[high] >= X) {
                    low = middle + 1;
                } else {
                    high = middle - 1;
                }
            }
        }

        return -1;
    }
}

3.3 时间复杂度分析

✅ 时间复杂度为 O(log N)，其中 N 是数组长度。
这是因为每次都将搜索空间减半，类似于标准的二分查找。

4. 小结

本文介绍了如何在一个排序并旋转的数组中高效查找目标值。我们通过分析数组的结构特性，巧妙地结合了二分查找思想，并给出了一个 Java 实现。

这种思路在实际开发中非常实用，尤其适用于处理数据结构中“有序但不完全连续”的情况。在面试中也常被用来考察候选人对算法的灵活运用能力。

⚠️ 踩坑提醒：不要直接使用线性查找，虽然逻辑简单，但效率低下，无法通过大规模数据测试。要掌握二分查找的变形逻辑，是解决这类问题的关键。

Persistence

REST

Security