如果您在二维数组上进行二分查找，matrix[mid/n][mid%n] 是如何给出中间值的？

Question

我正在努力理解以下内容solution from Leetcode：

def searchMatrix(self, matrix, target):
    n = len(matrix[0])
    lo, hi = 0, len(matrix) * n
    while lo < hi:
        mid = (lo + hi) / 2
        x = matrix[mid/n][mid%n]
        if x < target:
            lo = mid + 1
        elif x > target:
            hi = mid
        else:
            return True
    return False

matrix[mid/n][mid%n]如何给你中间值？

Answer 1

mid 是 m*n 矩阵的线性版本的索引。您需要将其转换为行和列索引。您看到的是给定 n 列的 q 的久为人知的转换：row = int(q / n)、col = q % n.

n = 10可能有助于查看；在这种情况下，mid 是直接的十进制数字。第一个数字是行，第二个是列。可视化：

 0  1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 ...

你知道这是怎么回事吗？十位数字 (row = mid // 10) 和个位数字 (col = mid % 10) 构成 10 列矩阵的索引。

Answer 2

这是一种以线性方式遍历数组并将线性索引转换为二维索引的方法。如果您有一个 3x3 阵列，则有 9 个单元格。在主要行（通过跨行创建线性索引）中，编号为 0-8，线性索引将如下所示：

0 1 2
3 4 5
6 7 8

二维索引为：

(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)

诀窍是 mid/n 是行，mid%n 是列。检查整个数组意味着检查所有 9 个元素。 4/3 是 1，中间。 4%3 也是 1，又是中间。就看知道/是整数除法，%是mod，还是整数除法后的余数

我认为这是一个很酷的问题，因为它同时使用了两种除法和从一维内存创建二维矩阵的方式。

如果您在二维数组上进行二分查找，matrix[mid/n][mid%n] 是如何给出中间值的？

If you're doing binary search on a 2D array, how does matrix[mid/n][mid%n] give you the middle value?

algorithm

binary-search

multidimensional-array