每日算法 — 使用java实现旋转数组：二分查找与边界判定算法

算法背景

旋转数组是将一个原本有序的数组在某一个下标处进行旋转（即将前面部分移到后面）得到的数组。例如 [0,1,2,4,5,6,7] 在下标3处旋转后变为 [4,5,6,7,0,1,2]。

旋转数组问题的核心挑战在于：数组局部有序但整体无序，传统的二分查找需要经过改造才能适用。经典的旋转数组问题包括：寻找最小值、搜索特定值、判断数组是否由有序数组旋转得到等。

核心思路

旋转数组有一个重要性质：将数组从中间切开后，至少有一半是有序的。利用这一性质，我们可以在O(log n)时间内完成搜索。

对于寻找最小值的问题：比较中间元素与右边界元素，若 nums[mid] > nums[right]，说明最小值在右半部分；若 nums[mid] < nums[right]，说明最小值在左半部分（包含mid）；若相等则无法判断，需要缩小右边界。

Java实现

/**
 * 旋转数组相关算法实现
 * 包含寻找最小值、搜索目标值、判断旋转次数等
 */
public class RotatedSortedArray {

    /**
     * 寻找旋转数组中的最小值
     * 数组无重复元素
     * 时间复杂度：O(log n)
     */
    public int findMin(int[] nums) {
        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]) {
                // 最小值在左半部分（包含mid）
                right = mid;
            }
            // 无重复元素时不会出现相等的情况
        }
        return nums[left];
    }

    /**
     * 寻找旋转数组中的最小值（含重复元素版本）
     * 最坏情况时间复杂度：O(n)，平均O(log n)
     */
    public int findMinWithDuplicates(int[] nums) {
        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 {
                // 相等时无法判断，保守地缩小右边界
                right--;
            }
        }
        return nums[left];
    }

    /**
     * 在旋转数组中搜索目标值
     * 时间复杂度：O(log n)
     */
    public int search(int[] nums, int target) {
        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]) {
                // 左半部分有序
                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 -1; // 未找到
    }

    /**
     * 计算数组的旋转次数（即最小值下标）
     * 时间复杂度：O(log n)
     */
    public int rotationCount(int[] nums) {
        int left = 0, right = nums.length - 1;
        int n = nums.length;

        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 {
                right--;
            }
        }
        return left;
    }

    /**
     * 判断数组是否由有序数组旋转得到
     */
    public boolean isRotatedSorted(int[] nums) {
        int n = nums.length;
        int count = 0; // 记录"断点"数量

        for (int i = 0; i < n; i++) {
            if (nums[i] > nums[(i + 1) % n]) {
                count++;
            }
            if (count > 1) return false;
        }
        return true;
    }

    /**
     * 主函数：测试与演示
     */
    public static void main(String[] args) {
        RotatedSortedArray rsa = new RotatedSortedArray();

        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("数组: [4,5,6,7,0,1,2]");
        System.out.println("最小值: " + rsa.findMin(nums));
        System.out.println("旋转次数: " + rsa.rotationCount(nums));
        System.out.println("搜索0的下标: " + rsa.search(nums, 0));
        System.out.println("搜索3的下标: " + rsa.search(nums, 3));
        System.out.println("是否为旋转有序数组: " + rsa.isRotatedSorted(nums));

        int[] dupNums = {2, 2, 2, 0, 1, 2};
        System.out.println("\n含重复数组: [2,2,2,0,1,2]");
        System.out.println("最小值: " + rsa.findMinWithDuplicates(dupNums));
    }
}

复杂度分析

应用场景

• 日志文件分析：循环缓冲区中的时间戳搜索
• 循环队列：在循环存储结构中高效定位元素
• 音乐播放列表：循环播放模式下的歌曲索引定位

总结

旋转数组问题是二分查找的经典变种。核心思想在于利用”至少一半有序”的性质，每次迭代都能确定目标所在的区间。本文提供了寻找最小值、搜索目标值、判断旋转次数等常见操作的Java实现，帮助读者掌握处理局部有序数据结构的二分查找技巧。