33. 搜索旋转排序数组

[此处请插入：二分查找过程中排除乱序区间的判断示意图]

✨核心逻辑

本题采用 二分查找 的策略，将时间复杂度优化至 O(log n)：

核心规律：虽然整个数组被旋转了，不再完全有序，但我们可以通过 nums[left] 和 nums[mid] 的大小关系，判断出其中哪一半是严格有序的。
分情况讨论：
- 情况 1：如果 nums[left] > nums[mid]，说明右半区 [mid, right] 是严格有序的。
- 情况 2：否则（nums[left] <= nums[mid]），说明左半区 [left, mid] 是严格有序的。
缩小范围：
- 在确认了哪半区有序后，判断目标值 target 是否落在该有序区的范围内。
- 如果在范围内，说明答案就在这个有序区中，直接移动指针逼近该区间。
- 如果不在范围内，说明答案在另一半区，排除当前有序区，向另一端搜索。

🔥代码实现（含详细变量注释）

class Solution {
    public int search(int[] nums, int target) {
        // left：二分查找的左边界指针，初始指向数组的第一个元素
        int left = 0;
        // right：二分查找的右边界指针，初始指向数组的最后一个元素
        int right = nums.length - 1;

        // 循环条件：当左边界指针小于等于右边界指针时，持续进行搜索
        while (left <= right) {
            // mid：计算当前搜索区间的中间索引，使用 left + (right - left) / 2 防止直接相加溢出
            int mid = left + (right - left) / 2;
            
            // 1. 基础命中：如果中间元素正好等于目标值，直接返回下标
            if (nums[mid] == target) {
                return mid;
            }

            // 2. 判断哪一侧是有序的
            // 如果左边界元素大于中间元素，说明左半区发生了旋转，右边半区 [mid, right] 是严格升序的
            if (nums[left] > nums[mid]) {
                // 判断目标值 target 是否在右侧有序半区内
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1; // 如果 target 在右侧，收缩左边界
                } else {
                    right = mid - 1; // 如果 target 不在右侧，目标在左侧，收缩右边界
                }
            } 
            // 否则，说明左半区 [left, mid] 是严格升序的
            else {
                // 判断目标值 target 是否在左侧有序半区内
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // 如果 target 在左侧，收缩右边界
                } else {
                    left = mid + 1;  // 如果 target 不在左侧，目标在右侧，收缩左边界
                }
            }
        }
        // 如果循环结束还没找到 target，说明数组中不存在该目标值，返回 -1
        return -1;
    }
}