每日算法 — 使用java实现机器人寻宝：旋转排序数组的二分查找与边界判定

问题背景

想象一个寻宝机器人，它面前是一个环形旋转密码盘。密码盘上的数字原本按升序排列，但被人为旋转了某个未知的位置。机器人需要通过二分查找算法，在O(log n)时间内找到最小值或特定宝藏的位置。

这一场景对应经典的”旋转排序数组”问题：将一个原本升序排列的数组从某处旋转后，如何在高效时间内完成搜索？该问题是二分查找的高级变体，广泛应用于循环缓冲区的定位、旋转图像的索引查找等实际场景。

问题描述

问题一：查找最小值（LeetCode 153）

给定一个升序排列的数组经过一次旋转后的结果，数组中无重复元素，找出其中的最小值。

问题二：查找目标值（LeetCode 33）

在旋转排序数组中搜索一个给定目标值，如果存在则返回索引，否则返回-1。

示例

• 输入：[3, 4, 5, 1, 2]，最小值为 1
• 输入：[4, 5, 6, 7, 0, 1, 2]，目标值 0 的索引为 4

核心思路：二分查找的适应性改造

旋转排序数组的关键性质是：它由两个有序子数组组成，且左子数组的所有元素都大于右子数组的最小元素。

判定旋转点位置

对于中间元素 nums[mid]：
– 若 nums[mid] > nums[right]，说明旋转点在右半区间，mid 左侧（含mid）属于左有序子数组
– 若 nums[mid] < nums[right]，说明旋转点在左半区间或就是mid，mid 右侧（含mid）属于右有序子数组

搜索目标值

当需要查找特定目标值时，每次先判断哪一半是有序的，再在有序区间内判断目标值是否落入其中。

Java完整实现

import java.util.Arrays;

/**
 * 旋转排序数组的二分查找系列问题
 * 包含查找最小值、查找目标值、含重复元素等变体
 */
public class RotatedSortedArraySearch {

    /**
     * 153. 寻找旋转排序数组中的最小值
     * 无重复元素版本
     * 时间复杂度：O(log n)  空间复杂度：O(1)
     */
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组为空");
        }

        int left = 0, right = nums.length - 1;

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

            // 与右边界比较，避免与左边界比较的歧义
            if (nums[mid] > nums[right]) {
                // mid在左有序数组中，最小值在右侧
                left = mid + 1;
            } else {
                // nums[mid] < nums[right]，mid在右有序数组中
                // 由于无重复元素，不可能相等
                // 最小值在左侧或就是mid本身
                right = mid;
            }
        }

        // left == right，找到最小值
        return nums[left];
    }

    /**
     * 154. 寻找旋转排序数组中的最小值II
     * 含重复元素版本
     * 时间复杂度：最坏O(n)，平均O(log n)  空间复杂度：O(1)
     */
    public int findMinWithDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组为空");
        }

        int left = 0, right = nums.length - 1;

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

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                // nums[mid] == nums[right]，无法判断旋转点在哪
                // 安全策略：缩小右边界
                right--;
            }
        }

        return nums[left];
    }

    /**
     * 33. 搜索旋转排序数组
     * 无重复元素，查找目标值的索引
     * 时间复杂度：O(log n)  空间复杂度：O(1)
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0, right = nums.length - 1;

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

            if (nums[mid] == target) {
                return mid;
            }

            // 判断哪一半是有序的
            if (nums[left] <= nums[mid]) {
                // 左半部分有序 [left, mid]
                if (target >= nums[left] && target < nums[mid]) {
                    // 目标在有序左半部分
                    right = mid - 1;
                } else {
                    // 目标在右半部分
                    left = mid + 1;
                }
            } else {
                // 右半部分有序 [mid, right]
                if (target > nums[mid] && target <= nums[right]) {
                    // 目标在有序右半部分
                    left = mid + 1;
                } else {
                    // 目标在左半部分
                    right = mid - 1;
                }
            }
        }

        return -1;  // 未找到
    }

    /**
     * 81. 搜索旋转排序数组II
     * 含重复元素，查找目标值是否存在
     * 时间复杂度：最坏O(n)，平均O(log n)  空间复杂度：O(1)
     */
    public boolean searchWithDuplicates(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int left = 0, right = nums.length - 1;

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

            if (nums[mid] == target) {
                return true;
            }

            // 处理重复元素的歧义情况
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }

            if (nums[left] <= nums[mid]) {
                // 左半部分有序
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 右半部分有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return false;
    }

    /**
     * 扩展：同时返回旋转点的索引（最小值的索引）
     */
    public int findMinIndex(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int left = 0, right = nums.length - 1;

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

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    /**
     * 扩展：恢复旋转数组（找到旋转点后排序）
     */
    public int[] restoreRotatedArray(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }

        int minIndex = findMinIndex(nums);
        if (minIndex == 0) {
            return nums.clone();  // 未旋转
        }

        int n = nums.length;
        int[] result = new int[n];

        // 从最小值位置开始按序复制
        for (int i = 0; i < n; i++) {
            result[i] = nums[(minIndex + i) % n];
        }

        return result;
    }

    /**
     * 扩展：查找旋转次数（即最小值的索引）
     */
    public int findRotationCount(int[] nums) {
        return findMinIndex(nums);
    }

    /**
     * 扩展：在旋转排序数组中使用递归实现搜索
     */
    public int searchRecursive(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        return searchRecursiveHelper(nums, 0, nums.length - 1, target);
    }

    private int searchRecursiveHelper(int[] nums, int left, int right, int target) {
        if (left > right) {
            return -1;
        }

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

        if (nums[mid] == target) {
            return mid;
        }

        if (nums[left] <= nums[mid]) {
            // 左半有序
            if (target >= nums[left] && target < nums[mid]) {
                return searchRecursiveHelper(nums, left, mid - 1, target);
            } else {
                return searchRecursiveHelper(nums, mid + 1, right, target);
            }
        } else {
            // 右半有序
            if (target > nums[mid] && target <= nums[right]) {
                return searchRecursiveHelper(nums, mid + 1, right, target);
            } else {
                return searchRecursiveHelper(nums, left, mid - 1, target);
            }
        }
    }

    // ============ 测试入口 ============
    public static void main(String[] args) {
        RotatedSortedArraySearch solution = new RotatedSortedArraySearch();

        // 测试查找最小值
        int[] nums1 = {3, 4, 5, 1, 2};
        int[] nums2 = {4, 5, 6, 7, 0, 1, 2};
        int[] nums3 = {11, 13, 15, 17};  // 未旋转
        int[] nums4 = {2, 2, 2, 0, 1};   // 含重复

        System.out.println("===== 查找最小值 =====");
        System.out.println("数组: " + Arrays.toString(nums1) + " -> 最小值: " + solution.findMin(nums1));
        System.out.println("数组: " + Arrays.toString(nums2) + " -> 最小值: " + solution.findMin(nums2));
        System.out.println("数组: " + Arrays.toString(nums3) + " -> 最小值: " + solution.findMin(nums3));
        System.out.println("数组: " + Arrays.toString(nums4) + " -> 最小值(含重复): " + solution.findMinWithDuplicates(nums4));

        // 测试搜索目标值
        System.out.println("\n===== 搜索目标值 =====");
        System.out.println("数组: " + Arrays.toString(nums1) + ", 目标1 -> 索引: " + solution.search(nums1, 1));
        System.out.println("数组: " + Arrays.toString(nums2) + ", 目标0 -> 索引: " + solution.search(nums2, 0));
        System.out.println("数组: " + Arrays.toString(nums2) + ", 目标3 -> 索引: " + solution.search(nums2, 3));

        // 测试恢复数组
        System.out.println("\n===== 恢复旋转数组 =====");
        System.out.println("原数组: " + Arrays.toString(nums1));
        System.out.println("恢复后: " + Arrays.toString(solution.restoreRotatedArray(nums1)));

        // 测试旋转次数
        System.out.println("\n===== 旋转次数 =====");
        System.out.println("数组: " + Arrays.toString(nums1) + " -> 旋转次数: " + solution.findRotationCount(nums1));
        System.out.println("数组: " + Arrays.toString(nums2) + " -> 旋转次数: " + solution.findRotationCount(nums2));
        System.out.println("数组: " + Arrays.toString(nums3) + " -> 旋转次数: " + solution.findRotationCount(nums3));

        // 测试递归搜索
        System.out.println("\n===== 递归搜索 =====");
        System.out.println("数组: " + Arrays.toString(nums2) + ", 目标6 -> 索引: " + solution.searchRecursive(nums2, 6));
    }
}

算法执行流程图解

以数组 [4, 5, 6, 7, 0, 1, 2] 查找最小值为例：

初始: left=0(值4), right=6(值2)
第1轮: mid=3(值7), 7>2 -> left=4
       范围: [0, 1, 2], left=4(值0), right=6(值2)
第2轮: mid=5(值1), 1<2 -> right=5
       范围: [0, 1], left=4(值0), right=5(值1)
第3轮: mid=4(值0), 0<1 -> right=4
       left=4 == right=4, 找到最小值 0

复杂度分析

关键技巧总结

1. 与右边界比较：找最小值时，比较 nums[mid] 与 nums[right] 而非 nums[left]，可以避免单元素和未旋转数组的边界问题
2. 有序区间判定：搜索目标值时，关键是先确定 [left, mid] 和 [mid, right] 哪个有序，再在有序区间内判断目标是否存在
3. 重复元素处理：当 nums[left] == nums[mid] == nums[right] 时无法判断，只能线性缩界，导致最坏O(n)
4. 防溢出写法：mid = left + (right - left) / 2 比 (left + right) / 2 更安全

扩展应用

1. 循环队列实现：利用旋转数组思想实现固定大小的循环缓冲区
2. 日志文件搜索：在按时间排序但发生回绕的日志中查找特定时间点的记录
3. 循环链表定位：在循环有序链表中查找特定值，思路完全一致
4. 峰值元素查找：在旋转数组中查找局部最大值（左半部分最后一个元素）