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

[Leviathann]

而且代码量多了好多倍，二维矩阵的对角线上二分查找那边界条件 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
        }
    }


}

[leonme]

是 kotlin 的代码的可读性本来就不好，还是。。。

[Leviathann]

@leonme 主要是所有进入递归和二分查找下一次循环的地方都要判定一下有没有到达预设的边界，如果 x 轴到达边界就会退化成 y 轴上的二分查找，y 轴也一样
然后在对角线上找相邻的两个点哪里必须返回两个坐标也就是四个值，我把每个坐标封装成一个 x 轴和 y 轴索引的 pair 但感觉也没提升什么可读性

[byteli]

我也是先去搞二分，各种 corner case 折磨的很难受，看了题解的右上解法发现也很快，就直接背下来了。
不过测时间用 kotlin 这种带虚拟机的是不是不合适

[Leviathann]

@byteli 是的啊 尤其是对角线二分查找那个地方，中止条件和返回时算左上点和右下点我完全是用他的测试用例调试出来的。。

[Leviathann]

@byteli 这个时间和空间应该都是同语言的去比的

[byteli]

@Leviathann 我意思是有 jvm 的话会不会受随机的影响很多呢，预热啊什么的