面试题 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();} }