什么是旋转排序数组？
考虑一个排序数组，例如：
[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 < 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)
}
}
守则解释
-
搜索():
- 该函数负责在旋转排序数组中搜索目标。
- 首先，我们使用 searchpivot() 函数找到 枢轴。
- 根据主元的位置，我们决定使用二分搜索来搜索数组的哪一半。
-
binarysearch():
立即学习“Java免费学习笔记（深入）”；
- 标准二分搜索算法，用于在排序的子数组中查找目标。
- 我们定义开始和结束索引并逐渐缩小搜索空间。
-
searchpivot():
- 此函数标识枢轴点（数组旋转的位置）。
- 主元是排序顺序被“破坏”的索引（即数组从较高值变为较低值）。
- 如果没有找到主元，则说明数组没有旋转，我们可以进行常规的二分查找。
算法如何工作
对于像 [4, 5, 6, 1, 2, 3] 这样的数组：
- 枢轴 位于索引 2（6 是最大的，其次是 1，最小）。
- 我们使用这个主元将数组分为两部分：[4, 5, 6] 和 [1, 2, 3]。
- 如果目标大于或等于第一个元素（本例中为 4），我们将搜索左半部分。否则，我们搜索右半部分。
此方法确保我们高效搜索，实现 o(log n) 的时间复杂度，类似于标准的二分搜索。
结论
旋转排序数组是一个常见的面试问题，也是加深您对二分搜索理解的有用挑战。通过找到枢轴并相应地调整我们的二分搜索，我们可以在对数时间中高效地搜索数组。
如果您觉得这篇文章有帮助，请随时在 linkedin 上与我联系或在评论中分享您的想法！快乐编码！
