什么是旋转排序数组？
考虑一个排序数组，例如：
[1, 2, 3, 4, 5, 6]
现在，如果这个数组在某个枢轴处旋转，比如在索引 3 处，它将变成：
[4, 5, 6, 1, 2, 3]
请注意，数组仍然是排序的，但它被分为两部分。我们的目标是有效地在此类数组中搜索目标值。
搜索策略
要在旋转排序数组中搜索，我们需要：
找到枢轴：枢轴是数组从较大值过渡到较小值的点。二分查找：一旦找到主元，我们就可以在数组的相应一半上使用二分查找。
分步代码解释
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 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) }}
守则解释
搜索():
该函数负责在旋转排序数组中搜索目标。首先，我们使用 searchpivot() 函数找到 枢轴。根据主元的位置，我们决定使用二分搜索来搜索数组的哪一半。
binarysearch():
立即学习“Java免费学习笔记（深入）”；
纳米搜索
纳米搜索：360推出的新一代AI搜索引擎
30 查看详情 
标准二分搜索算法，用于在排序的子数组中查找目标。我们定义开始和结束索引并逐渐缩小搜索空间。
searchpivot():
此函数标识枢轴点（数组旋转的位置）。主元是排序顺序被“破坏”的索引（即数组从较高值变为较低值）。如果没有找到主元，则说明数组没有旋转，我们可以进行常规的二分查找。
算法如何工作
对于像 [4, 5, 6, 1, 2, 3] 这样的数组：
枢轴 位于索引 2（6 是最大的，其次是 1，最小）。我们使用这个主元将数组分为两部分：[4, 5, 6] 和 [1, 2, 3]。如果目标大于或等于第一个元素（本例中为 4），我们将搜索左半部分。否则，我们搜索右半部分。
此方法确保我们高效搜索，实现 o(log n) 的时间复杂度，类似于标准的二分搜索。
结论
旋转排序数组是一个常见的面试问题，也是加深您对二分搜索理解的有用挑战。通过找到枢轴并相应地调整我们的二分搜索，我们可以在对数时间中高效地搜索数组。
如果您觉得这篇文章有帮助，请随时在 linkedin 上与我联系或在评论中分享您的想法！快乐编码！
以上就是用 Java 构建旋转排序数组搜索：了解枢轴搜索和二分搜索的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/463954.html
微信扫一扫 
支付宝扫一扫 
