特殊矩阵的二分搜索

行列上有序的矩阵采用分治法进行递归搜索 O(log2N)

矩阵分治法搜索

○思考

前提条件：n*n 的矩阵对于每一行有序，对于每一列有序。

**算法思想：**采用分治法 参考一维数组的二分搜索思路，根据子矩阵的最小值在左上角，最大值在右下角通过不断划分最终将定位到1*1也就是单个元素上，每次将矩阵划分为四块。

○实现

import cn.hutool.core.text.StrJoiner;
import cn.hutool.core.util.StrUtil;

public class MatrixBinarySearch {
    public static void main(String[] args) {
        int[][] m = new int[][]{
                {0, 2, 4, 6},
                {1, 5, 7, 8},
                {3, 10, 11, 21},
                {9, 13, 15, 24}
        };
        int n = m.length;
        boolean b = binarySearch(m, 0, 0, n, 6);
        System.out.println(b);
    }

    public static boolean binarySearch(int[][] matrix, int startRow, int startCol,  int size, int target) {
        int min = matrix[startRow][startCol];
        int max = matrix[startRow + size - 1][startCol + size - 1];
        //出口一 不在范围内
        if (target < min || target > max) {
            return false;
        }
        //出口二 边界值是目标值 （少数情况）
        if (target == min) {
            System.out.println(StrUtil.format("found in ({},{})", startRow, startCol));
            return true;
        } else if (target == max) {
            System.out.println(StrUtil.format("found in ({},{})", startRow + size - 1, startCol + size -1));
            return true;
        }
        //出口三 递归终点
        if (size == 1) {
            if (matrix[startRow][startCol] == target) {
                System.out.println(StrUtil.format("found in ({},{})", startRow, startCol));
                return true;
            } else {
                System.out.println("not found");
                return false;
            }
        }
        int s = size / 2;
        int centerRow = startRow + s;
        int centerCol = startCol + s;
        //奇数矩阵需共用一条边
        s = size % 2 == 0 ? s : s + 1;
        return  //递归搜索左上矩阵
                binarySearch(matrix, startRow, startCol, s, target) ||
                //递归搜索右上矩阵
                binarySearch(matrix, startRow, centerCol, s, target) ||
                //递归搜索左下矩阵
                binarySearch(matrix, centerRow, startRow, s, target) ||
                //递归搜索右下矩阵
                binarySearch(matrix, centerRow, centerCol, s, target);
    }
}