66.搜索旋转数组

面试题 10.03. 搜索旋转数组

 搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例 1：

 输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 输出：8（元素5在该数组中的索引）

 

 

 

 

核心二分逻辑  来源：乐清

预处理：判断数组是否为空，空则直接返回 

1避免空指针异常

2循环内优先检查左边界：若 arr[left] == target，直接返回 left保证找到的是最小索引

 ① 若 arr[mid] == target → right=mid（左侧可能有更小索引）；

 ② 若 arr[0] < arr[mid]（左半区有序）：

 　　- 目标值在左半区 → right=mid-1；

 　　- 否则 → left=mid+1；

 ③ 若 arr[0] > arr[mid]（右半区有序）：

　　- 目标值在右半区 → left=mid+1；

　　- 否则 → right=mid-1；

④ 若 arr[0] == arr[mid]（无法判断有序）→ left++逐步缩小查找范围，逼近目标5循环结束（left>right），返回 -1目标值不存在

2. 为什么必须优先检查 left？

如果去掉这行代码，会出现两个问题：

• 无法保证「最小索引」：比如数组 arr = [1,0,1,1,1]，target=0，若不检查 left，可能先找到 mid 位置的 1，再收缩边界，最终虽然能找到 0，但逻辑冗余；
• 效率降低：明明已经找到最小索引，却还要继续循环，浪费计算资源。

3. 为什么要 left++？

• 「无法判断有序区间」时，无法通过 mid 收缩右边界（比如不知道目标值在左还是右）；
• 而 arr[left] 已经检查过不等于 target（因为开头先判断了 arr[left] == target），所以可以安全地把 left 右移一位，缩小查找范围；
• 若不 left++，会导致 left 和 right 永远不变，进入死循环。

class Solution {
    public int search(int[] arr, int target) {
        // 处理空数组边界情况
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int n = arr.length;
        int left = 0;          // 左边界：初始化为数组第一个元素下标
        int right = n - 1;     // 右边界：初始化为数组最后一个元素下标

        // 二分查找核心循环：缩小查找范围，直到左边界超过右边界
        while (left <= right) {
            // 核心优化1：左边界匹配直接返回（保证找到的是最小索引）
            // 因为left是当前遍历到的最小候选下标，匹配则无需继续查找
            if (arr[left] == target) {
                return left;
            }

            // 计算中间下标：用 left + (right-left)/2 而非 (left+right)/2，避免整数溢出
            int mid = left + (right - left) / 2;

            // 核心逻辑1：中间值匹配目标值 → 收缩右边界到mid（左侧可能有更小索引的目标值）
            if (arr[mid] == target) {
                right = mid;
            }
            // 核心逻辑2：左半区是严格有序的（arr[0] < arr[mid]）
            else if (arr[0] < arr[mid]) {
                // 目标值在左半区（有序区间）→ 收缩右边界
                if (arr[0] <= target && target < arr[mid]) {
                    right = mid - 1;
                }
                // 目标值在右半区（旋转区间）→ 收缩左边界
                else {
                    left = mid + 1;
                }
            }
            // 核心逻辑3：右半区是严格有序的（arr[0] > arr[mid]）
            else if (arr[0] > arr[mid]) {
                // 目标值在右半区（有序区间）→ 收缩左边界
                if (arr[mid] < target && target <= arr[right]) {
                    left = mid + 1;
                }
                // 目标值在左半区（旋转区间）→ 收缩右边界
                else {
                    right = mid - 1;
                }
            }
            // 核心逻辑4：arr[0] == arr[mid]（处理重复元素，无法判断哪半区有序）
            else {
                // 左边界右移，缩小查找范围（避免死循环）
                left++;
            }
        }

        // 循环结束未找到目标值
        return -1;
    }
}

【超级麻烦的边界，arr[left] == target 和left++想半天想不懂】

【背吧】

 

class Solution {
    public int search(int[] arr, int target) {
        List<Pair<Integer, Integer>> pairs = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            Pair<Integer, Integer> pair = new Pair<>(i, arr[i]);
            pairs.add(pair);
        }
        pairs.sort(Comparator.comparingInt(Pair::getValue));

        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (pairs.get(mid).getValue() >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (pairs.get(left).getValue() != target) return -1;
        return pairs.get(left).getKey();
    }
}