用 Java 构建旋转排序数组搜索：了解枢轴搜索和二分搜索

什么是旋转排序数组？

考虑一个排序数组，例如：

[1, 2, 3, 4, 5, 6]

现在，如果这个数组在某个枢轴处旋转，比如在索引 3 处，它将变成：

[4, 5, 6, 1, 2, 3]

请注意，数组仍然是排序的，但它被分为两部分。我们的目标是有效地在此类数组中搜索目标值。

---

搜索策略

要在旋转排序数组中搜索，我们需要：

1. 找到枢轴：枢轴是数组从较大值过渡到较小值的点。
2. 二分查找：一旦找到枢轴，我们就可以在数组的相应一半上使用二分查找。

---

分步代码解释

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: " + result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot + 1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (arr[mid] == target) {
                return mid; // Target found
            } else if (target < arr[mid]) {
                end = mid - 1; // Search left half
            } else {
                start = mid + 1; // Search right half
            }
        }
        return -1; // Target not found
    }

    // Function to find the pivot index in a rotated sorted array
    static int searchPivot(int[] arr) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            // Check if mid is the pivot point
            if (mid < end && arr[mid] > arr[mid + 1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }

            // Decide whether to move left or right
            if (arr[mid] <= arr[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return -1; // No pivot found (array is not rotated)
    }
}

---

守则解释

1. 搜索():

   • 该函数负责在旋转排序数组中搜索目标。
   • 首先，我们使用 searchPivot() 函数找到 枢轴。
   • 根据主元的位置，我们决定使用二分搜索来搜索数组的哪一半。

2. binarySearch():

   • 标准二分搜索算法，用于在排序的子数组中查找目标。
   • 我们定义开始和结束索引并逐渐缩小搜索空间。

3. searchPivot():

   • 此函数标识枢轴点（数组旋转的位置）。
   • 主元是排序顺序被“破坏”的索引（即数组从较高值变为较低值）。
   • 如果没有找到主元，则说明数组没有旋转，我们可以进行常规的二分查找。

---

算法如何工作

对于像 [4, 5, 6, 1, 2, 3] 这样的数组：

• 枢轴 位于索引 2（6 是最大的，其次是 1，最小）。
• 我们使用这个主元将数组分为两部分：[4, 5, 6] 和 [1, 2, 3]。
• 如果目标大于或等于第一个元素（本例中为 4），我们将搜索左半部分。否则，我们搜索右半部分。

此方法确保我们高效搜索，实现 O(log n) 的时间复杂度，类似于标准的二分搜索。

---

结论

旋转排序数组是一个常见的面试问题，也是加深您对二分搜索理解的有用挑战。通过找到枢轴并相应地调整我们的二分搜索，我们可以在对数时间中高效地搜索数组。

如果您觉得这篇文章有帮助，请随时在 LinkedIn 上与我联系或在评论中分享您的想法！快乐编码！

以上是用 Java 构建旋转排序数组搜索：了解枢轴搜索和二分搜索的详细内容。更多信息请关注PHP中文网其他相关文章！