用 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  arr[mid + 1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] 




<hr><h3>
  
  
  守则解释
</h3>

<ol>
<li>
<p><strong>搜索()</strong>:</p>

<ul>
<li>该函数负责在旋转排序数组中搜索目标。</li>
<li>首先，我们使用它 searchpivot() 函数找到 <strong>枢轴</strong>。</li>
<li>首先，我们使用它 searchpivot() 函数找到 <strong>枢轴</strong>。</li>
<li>根据主元的位置，我们决定用二分搜索来搜索数组的哪一半。</li>
</ul>
</li>
<li>
<p><strong>binarysearch()</strong>:</p>
<p><span>立即学习</span>“<a href="https://pan.quark.cn/s/c1c2c2ed740f" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">Java免费学习笔记(深入)</a>”；</p>

<ul>
<li>标准二分搜索算法，用于在排序的子数组中找到目标。</li>
<li>我们定义索引的开始和结束，并逐渐缩小搜索空间。</li>
</ul>
</li>
<li>
<p><strong>searchpivot()</strong>:</p>

<ul>
<li>该函数识别枢轴点(数组旋转位置)。</li>
<li>主要是排序顺序被“破坏”的索引(即数组从较高值变为较低值)。</li>
<li>主要是排序顺序被“破坏”的索引(即数组从较高值变为较低值)。</li>
<li>如果找不到主元，说明数组没有旋转，可以进行常规二分搜索。</li>
</ul>
</li>
</ol><hr><h3>
  
  
  如何工作算法？
</h3>

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

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

这种方法保证了我们的高效搜索和实现 o(log n) 时间复杂，类似于标准的二分搜索。

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

如果你认为这篇文章有帮助，请随时在那里 linkedin 联系我或在评论中分享你的想法！快乐编码！

以上就是用 Java 构建旋转排序数组搜索：了解枢轴搜索和二分搜索的详细信息，请关注图灵教育的其他相关文章！