如何在循环有序二维数组中实现对数时间复杂度的元素查找

核心思路 #

这类循环有序方阵的核心特征是：每次可拆分为4个边长为原边长1/2的同结构子象限，每个子象限的数值范围是连续的且可通过固定位置快速获取最值。每次查找时只需将目标值与4个象限的最值对比，即可确定目标值所在的子象限，将搜索范围直接缩小1/4，每次迭代边长减半，最终时间复杂度稳定为O(log n)。
你现有代码的核心问题在于加入了大量无规律的坐标偏移逻辑，边界判断混乱导致部分场景覆盖不到，只需去掉冗余偏移逻辑，严格按象限范围筛选即可解决。

完整实现代码 #

public class Circular2DSearch {
    // 测试用例数组
    static int[][] mat = {
            {1, 2, 3, 4, 17, 18, 19, 20},
            {8, 7, 6, 5, 24, 23, 22, 21},
            {12, 11, 10, 9, 28, 27, 26, 25},
            {16, 15, 14, 13, 32, 31, 30, 29},
            {49, 50, 51, 52, 33, 34, 35, 36},
            {56, 55, 54, 53, 40, 39, 38, 37},
            {60, 59, 58, 57, 45, 46, 41, 42},
            {64, 63, 62, 61, 48, 47, 44, 43}};

    public static boolean search(int[][] mat, int target) {
        int n = mat.length;
        // 全局最值判断，提前剪枝
        int globalMin = mat[0][0];
        int globalMax = mat[n-1][0];
        if (target < globalMin || target > globalMax) {
            return false;
        }
        // 当前搜索区域的左上角坐标，初始为(0,0)，边长为n
        int startX = 0, startY = 0, size = n;
        while (size >= 1) {
            // 边长为1时直接判断
            if (size == 1) {
                if (mat[startX][startY] == target) {
                    System.out.println("num=" + target);
                    System.out.println("row=" + startX);
                    System.out.println("col=" + startY);
                    return true;
                }
                return false;
            }
            int half = size / 2;
            // 计算四个象限的最值
            int minS1 = mat[startX][startY];
            int maxS1 = mat[startX + half - 1][startY];
            int minS2 = mat[startX][startY + half];
            int maxS2 = mat[startX + half - 1][startY + half];
            int minS3 = mat[startX + half][startY + half];
            int maxS3 = mat[startX + size - 1][startY + half];
            int minS4 = mat[startX + half][startY];
            int maxS4 = mat[startX + size - 1][startY];
            // 判断目标所在象限，切换搜索区域
            if (target >= minS1 && target <= maxS1) {
                // 左上象限，坐标不变，边长减半
                size = half;
            } else if (target >= minS2 && target <= maxS2) {
                // 右上象限，Y轴偏移half
                startY += half;
                size = half;
            } else if (target >= minS3 && target <= maxS3) {
                // 右下象限，X、Y都偏移half
                startX += half;
                startY += half;
                size = half;
            } else if (target >= minS4 && target <= maxS4) {
                // 左下象限，X轴偏移half
                startX += half;
                size = half;
            } else {
                // 不在四个象限范围内，不存在
                return false;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // 测试用例
        search(mat, 41); // 输出row=6, col=6
        search(mat, 64); // 输出row=7, col=0
        search(mat, 13); // 输出row=3, col=3
        search(mat, 99); // 返回false
    }
}

适配说明 #

该实现可兼容任意符合该循环有序特性的n阶方阵，无需额外修改逻辑，边长为奇数的场景也可正常适配，每次拆分向下取整即可。

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