leetcode 240 二维二分查找的解法速度好像还不如直接左下或者右上线性查找的解法 kotlin 时间 43% 内存 22%

而且代码量多了好多倍，二维矩阵的对角线上二分查找那边界条件 debug 了半天才写对
思路是在对角线上找到 a < target < b 的相邻值 a 和 b，a 的左上角所有元素都小于 target，b 的右下角所有元素都大于 target，然后递归的在右上和左下找

实际就是官方解法 3 的拓展提到的解法，翻了下题解区好像都没找到实现了这种解法的
我一开始的思路就是这个，写到一半感觉太麻烦就想翻答案看看是不是想错了，结果发现官方也只把这个作为拓展

class Solution {

    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        if (matrix.isEmpty() || matrix[0].isEmpty()) {
            return false
        }
        return searchSubMatrix(matrix, target, 0, matrix[0].size - 1, 0, matrix.size - 1)
    }

    private fun searchSubMatrix(
        matrix: Array<IntArray>,
        target: Int,
        xmin: Int,
        xmax: Int,
        ymin: Int,
        ymax: Int
    ): Boolean {
        if (xmin == xmax && ymin == ymax) {
            return retrieveValAtPos(matrix, Pair(xmin, ymin)) == target
        }
        val (upLeftBound, downRightBound) = findRange(matrix, target, xmin, xmax, ymin, ymax) ?: return true
        return searchSubMatrix(
            matrix,
            target,
            if (upLeftBound.first + 1 > xmax) xmax else upLeftBound.first + 1,
            xmax,
            ymin,
            if (downRightBound.second - 1 < ymin) ymin else downRightBound.second - 1
        ) || searchSubMatrix(
            matrix,
            target,
            xmin,
            if (downRightBound.first - 1 < xmin) xmin else downRightBound.first - 1,
            if (upLeftBound.second + 1 > ymax) ymax else upLeftBound.second + 1,
            ymax,
        )
    }

    private fun retrieveValAtPos(matrix: Array<IntArray>, pos: Pair<Int, Int>): Int {
        return matrix[pos.second][pos.first]
    }

    private fun findRange(
        matrix: Array<IntArray>,
        target: Int,
        xmin: Int,
        xmax: Int,
        ymin: Int,
        ymax: Int
    ): Pair<Pair<Int, Int>, Pair<Int, Int>>? {
        var lower = Pair(xmin, ymin)
        var upper = Pair(xmax, ymax)
        var center: Pair<Int, Int>
        var centerVal: Int
        while (lower.first < upper.first || lower.second < upper.second) {
            center = Pair(
                lower.first + (upper.first - lower.first) / 2,
                lower.second + (upper.second - lower.second) / 2
            )
            centerVal = retrieveValAtPos(matrix, center)
            when {
                centerVal > target -> {
                    upper = Pair(
                        if (upper.first == xmin) xmin else upper.first - 1,
                        if (upper.second == ymin) ymin else upper.second - 1
                    )
                }
                centerVal < target -> {
                    lower = Pair(
                        if (lower.first == xmax) xmax else lower.first + 1,
                        if (lower.second == ymax) ymax else lower.second + 1
                    )
                }
                else -> {
                    return null
                }
            }
        }
        when {
            retrieveValAtPos(matrix, lower) > target -> {
                return Pair(
                    Pair(
                        if (upper.first == xmin) xmin else upper.first - 1,
                        if (upper.second == ymin) ymin else upper.second - 1
                    ),
                    lower
                )
            }
            retrieveValAtPos(matrix, lower) < target -> {
                return Pair(
                    lower,
                    Pair(
                        if (lower.first == xmax) xmax else lower.first + 1,
                        if (lower.second == ymax) ymax else lower.second + 1
                    )
                )
            }
            else -> return null
        }
    }


}