如果您要在2D数组上进行二进制搜索，那么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矩阵的线性版本的索引。您需要将其转换为行和列索引。给定q列，您将看到n的长期转换：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 ...

你知道那是怎么回事吗？十位数字（行=中间// 10）和一位数字（col =中间％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，或整数除法后的余数。

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