33. 搜索旋转排序数组

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

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

例如，给定一个旋转排序数组 `[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 }
}