如何在圆形有序n×n二维数组中找pivot实现O(n log n)效率的搜索

一、象限拆分规则与边界确定 #

首先明确圆形有序矩阵的核心特征：矩阵按环分层，每层元素顺时针递增，且外层所有元素均小于内层所有元素。
你代码中未定义的i实际为矩阵的中心索引，计算方式为：int mid = matrix.length / 2，以此为分割点四个象限的边界、对应对比pivot如下：

• 第一象限（左上区域）
  • 行范围：[0, mid - 1]，列范围：[0, mid - 1]
  • 对比pivot：最小值为matrix[0][0]，最大值为matrix[mid-1][mid-1]
  • 内部规律：每行元素从左到右严格递增，可直接对每行做二分查找
• 第二象限（右上区域）
  • 行范围：[0, mid - 1]，列范围：[mid, n - 1]（n为矩阵阶数，即matrix.length）
  • 对比pivot：最小值为matrix[0][mid]，最大值为matrix[mid-1][n-1]
  • 内部规律：每行元素从左到右严格递增
• 第三象限（左下区域）
  • 行范围：[mid, n - 1]，列范围：[0, mid - 1]
  • 对比pivot：最小值为matrix[mid][0]，最大值为matrix[n-1][mid-1]
  • 内部规律：每行元素从左到右严格递增
• 第四象限（右下区域）
  • 行范围：[mid, n - 1]，列范围：[mid, n - 1]
  • 对比pivot：最小值为matrix[mid][mid]，最大值为matrix[n-1][n-1]
  • 内部规律：每行元素从左到右严格递增

注：如果n为奇数，中心元素matrix[mid][mid]单独判断是否等于目标值即可

二、修正后可运行的代码框架 #

public static boolean search(int matrix[][], int key) {
    int n = matrix.length;
    if (n == 0) return false;
    int mid = n / 2;
    // 奇数阶矩阵单独判断中心元素
    if (n % 2 == 1 && matrix[mid][mid] == key) return true;
    
    // 检查第一象限
    if (key >= matrix[0][0] && key <= matrix[mid-1][mid-1]) {
        for (int i = 0; i < mid; i++) {
            if (binarySearchRow(matrix[i], 0, mid-1, key)) {
                return true;
            }
        }
    }
    // 检查第二象限
    if (key >= matrix[0][mid] && key <= matrix[mid-1][n-1]) {
        for (int i = 0; i < mid; i++) {
            if (binarySearchRow(matrix[i], mid, n-1, key)) {
                return true;
            }
        }
    }
    // 检查第三象限
    if (key >= matrix[mid][0] && key <= matrix[n-1][mid-1]) {
        for (int i = mid; i < n; i++) {
            if (binarySearchRow(matrix[i], 0, mid-1, key)) {
                return true;
            }
        }
    }
    // 检查第四象限
    if (key >= matrix[mid][mid] && key <= matrix[n-1][n-1]) {
        for (int i = mid; i < n; i++) {
            if (binarySearchRow(matrix[i], mid, n-1, key)) {
                return true;
            }
        }
    }
    // 所有象限都没找到
    return false;
}

// 辅助方法：对单行的指定区间做二分查找
private static boolean binarySearchRow(int[] row, int left, int right, int key) {
    while (left <= right) {
        int midIdx = left + (right - left) / 2;
        if (row[midIdx] == key) return true;
        else if (row[midIdx] < key) left = midIdx + 1;
        else right = midIdx - 1;
    }
    return false;
}

三、时间复杂度说明 #

每个象限最多有n/2行，每行二分查找时间为O(log n)，四个象限总时间为4 * (n/2) * logn = O(n logn)，满足性能要求，远优于O(n²)的暴力查找。

内容的提问来源于stack exchange，提问作者anton5450