Если вы выполняете бинарный поиск в двумерном массиве, как матрица [mid / n] [mid% n] дает вам среднее значение?

Question

Я пытаюсь понять следующее решение из 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

Это способ обхода массива линейным способом и преобразования из линейного индекса в двумерные индексы в массив. Если у вас есть массив 3х3, у вас есть 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, опять же середина. Это зависит от знания того, что / - целочисленное деление, а% - мод, или остаток после целочисленного деления.

Я думаю, что это крутая проблема, потому что он использует оба вида деления и способ создания 2d матриц. одномерной памяти.

Answer 2

mid - индекс линейной версии матрицы m * n. Вы должны преобразовать это в индексы строк и столбцов. То, что вы видите, является давно известным преобразованием для q данных n столбцов: row = int(q / n), col = q % n.

. Это может помочь просмотреть это при n = 10; в этом случае mid является простым числом с основанием десять. Первый di git - это строка, второй - столбец. Визуализируйте:

 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 ...

Вы видите, как это работает? Десятки di git (строка = mid // 10) и единицы di git (col = mid% 10) образуют индексы в матрице из 10 столбцов.