当前位置:实例文章 » 其他实例» [文章]33. 搜索旋转排序数组

33. 搜索旋转排序数组

发布人:shili8 发布时间:2025-03-15 06:57 阅读次数:0

**搜索旋转排序数组**

在本文中,我们将讨论如何在一个旋转排序数组中进行搜索。旋转排序数组是指一个已经排好序的数组,但其中的一些元素被旋转到了数组的另一端。

例如,给定一个旋转排序数组 `[4,5,6,7,0,1,2]`,我们需要找到数字 `0` 的位置。这个问题看起来很简单,但是如果我们使用二分查找法来解决它,就会发现有很多陷阱。

**旋转排序数组的定义**

一个旋转排序数组是指一个长度为 `n` 的整数数组 `arr[]`,其中所有元素都在范围 `[0, n-1]` 内。这个数组经过旋转操作后,变成了一个新的数组 `new_arr[]`,其中所有元素依然在范围 `[0, n-1]` 内。

**搜索旋转排序数组的方法**

我们可以使用二分查找法来解决这个问题,但是需要注意的是,我们不能直接使用标准的二分查找法,因为旋转排序数组可能是反向排列的。因此,我们需要对标准的二分查找法进行一些修改。

以下是搜索旋转排序数组的方法:

1. **找到中间元素**:首先,我们需要找到中间元素 `mid`,使得 `arr[mid]` 等于 `target`。
2. **判断中间元素是否等于目标值**:如果 `arr[mid]` 等于 `target`,则直接返回 `mid`。
3. **判断左半部分是否有序**:如果 `arr[0] <= arr[mid]`,则意味着左半部分是有序的。如果 `arr[0] > arr[mid]`,则意味着右半部分是有序的。
4. **递归搜索**:根据上一步的结果,我们可以决定是否继续递归搜索左半部分或右半部分。

以下是使用 Java语言编写的示例代码:

javapublic class SearchRotatedSortedArray {
 public int search(int[] nums, int target) {
 // Base case: If the array is empty, return -1.
 if (nums.length ==0) {
 return -1;
 }

 // Find the middle element of the array.
 int mid = nums.length /2;

 // If the middle element is equal to the target, return its index.
 if (nums[mid] == target) {
 return mid;
 }

 // If the left half is sorted.
 if (nums[0] <= nums[mid]) {
 // If the target is in the range of the left half, search it there.
 if (nums[0] <= target && target < nums[mid]) {
 return searchRange(nums,0, mid -1, target);
 } else {
 // Otherwise, search it in the right half.
 return searchRange(nums, mid +1, nums.length -1, target);
 }
 }

 // If the right half is sorted.
 else {
 // If the target is in the range of the right half, search it there.
 if (nums[mid] < target && target <= nums[nums.length -1]) {
 return searchRange(nums, mid +1, nums.length -1, target);
 } else {
 // Otherwise, search it in the left half.
 return searchRange(nums,0, mid -1, target);
 }
 }
 }

 private int searchRange(int[] nums, int start, int end, int target) {
 while (start <= end) {
 int mid = start + (end - start) /2;
 if (nums[mid] == target) {
 return mid;
 } else if (nums[mid] < target) {
 start = mid +1;
 } else {
 end = mid -1;
 }
 }

 // If the target is not found, return -1.
 return -1;
 }

 public static void main(String[] args) {
 SearchRotatedSortedArray solution = new SearchRotatedSortedArray();
 int[] nums = {4,5,6,7,0,1,2};
 int target =0;
 int result = solution.search(nums, target);
 System.out.println("Result: " + result); // Output:4 }
}


在这个示例中,我们首先找到中间元素 `mid`,然后判断左半部分是否有序。如果左半部分是有序的,我们可以决定是否继续递归搜索左半部分或右半部分。最后,我们使用二分查找法来找到目标值。

**总结**

在本文中,我们讨论了如何在一个旋转排序数组中进行搜索。我们首先定义了旋转排序数组的概念,然后介绍了一个方法来解决这个问题。该方法首先找到中间元素,判断左半部分是否有序,如果有序,则决定是否继续递归搜索左半部分或右半部分。如果没有序,则直接使用二分查找法来找到目标值。

我们还提供了一个 Java语言编写的示例代码,以便读者可以更好地理解这个方法。

其他信息

其他资源

Top