25. 搜索旋转排序数组：在旋转排序数组中搜索一个给定的目标值

在旋转排序数组中搜索一个给定的目标值是一个经典的二分查找变种问题。旋转排序数组是指一个有序数组在某个点被旋转后形成的数组。我们可以使用二分查找来实现这一问题。

一、问题描述

给定一个升序排列的整数数组 nums，它已被旋转过，且一个目标值 target，你需要在数组中找到该目标值，并返回其索引。如果目标值不在数组中，返回 -1。

二、解决思路

由于数组的某个部分是有序的，我们可以利用二分查找来缩小搜索范围。每次查找时，通过比较中间元素与左右边界的元素，可以判断出哪一部分是有序的，然后决定目标值是否在这个有序部分，从而进一步缩小查找范围。

三、代码实现

public class SearchRotatedSortedArray {

    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 检查中间元素是否是目标值
            if (nums[mid] == target) {
                return mid;
            }

            // 判断左半部分是否有序
            if (nums[left] <= nums[mid]) {
                // 判断目标值是否在左半部分
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // 在左半部分查找
                } else {
                    left = mid + 1; // 在右半部分查找
                }
            }
            // 否则右半部分一定有序
            else {
                // 判断目标值是否在右半部分
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1; // 在右半部分查找
                } else {
                    right = mid - 1; // 在左半部分查找
                }
            }
        }

        // 如果没有找到目标值，返回 -1
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 0;

        int result = search(nums, target);
        System.out.println("The index of target " + target + " is: " + result);
    }
}

四、代码详解

• 初始化左右指针：left 指向数组的起始位置，right 指向数组的末尾位置。
• 二分查找：在循环中，计算中间位置 mid。然后检查 nums[mid] 是否等于目标值 target，如果相等则返回 mid。
• 判断哪一半是有序的：
  • 如果 nums[left] <= nums[mid]，则左半部分是有序的。
  • 如果 nums[mid] < nums[right]，则右半部分是有序的。
• 缩小搜索范围：
  • 如果目标值在有序部分内，则缩小搜索范围到有序部分，否则搜索另一部分。
• 返回结果：如果找到了目标值，返回其索引；如果循环结束后仍未找到，返回 -1。

五、时间复杂度和空间复杂度

• 时间复杂度：O(log n)，其中 n 是数组的长度。该算法利用了二分查找，能够在对数时间内缩小搜索范围。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

六、总结

该算法利用了旋转排序数组的部分有序特性，通过二分查找实现了高效的搜索操作。与传统的二分查找相比，此方法通过判断哪一半部分是有序的，从而决定搜索的范围，有效地处理了旋转后的复杂情况。

这种方法适用于在部分有序的数组中进行搜索，是处理类似问题的经典解法。