Поиск числа в матрице на собеседованиях

Ходят слухи, что в одной известной зарубежной IT-компании на собеседованиях дают задачу на поиск числа в матрице. 🙂 В этой статье мы разберём несколько вариантов решения данной задачи.

Что такое матрица? Простыми словами — это набор чисел, записанных в строчки и столбики. Для наглядности можно представить матрицу в виде таблицы с числами:

Таблица в задаче даётся не простая — все числа отсортированы так, что в каждой строке и в каждом столбце числа расположены в порядке возрастания. Требуется найти указанное число в таблице, предложив наиболее быстрое решение.

Предположим, что нам требуется найти число 24. Однако, казалось бы, зачем нам вообще что-то решать и находить число 24, потому что вот же оно — третье по счёту в четвёртой строке! 😁

Ну, во-первых, потому что это задача по программированию, а во вторых — давайте представим, что вместо чисел мы имеем таблички с цифрами, которые стоят в ячейках стеллажа в комнате. Стеллаж у нас выступает аналогом таблицы выше.

Все таблички повёрнуты цифрами к стене. Мы лишь знаем условие: числа на табличках расположены в порядке возрастания, если смотреть слева направо или сверху вниз. Нам же необходимо, открывая таблички и узнавая цифру на них, найти искомое число как можно быстрее.

Давайте сразу отбросим вариант рандомного поиска, так как он всегда даёт разные результаты — не будем, пожалуй, считать это вариантом решения задачи с собеседования по программированию. 🙂

Первое и самое простое решение, которое может прийти в голову — просто перебрать по порядку слева направо все ячейки нашего «стеллажа», начиная с верхнего ряда.

Ниже пример кода такого решения на языке программирования Python:

def search_value(arr, value):
    if len(arr) == 0 or len(arr[0]) == 0 or not isinstance(value, int):
        return False
    m = len(arr)
    n = len(arr[0])
    for i in range(0, m):
        for j in range(0, n):
            if arr[i][j] == value:
                return True
    return False


matrix_arr = [
    [12, 14, 17, 21, 25, 26],
    [13, 15, 18, 22, 29, 32],
    [14, 16, 19, 26, 32, 34],
    [20, 23, 24, 27, 34, 37],
    [28, 31, 33, 36, 40, 46]
]

print(search_value(matrix_arr, 24))  # True

Такое решение вполне рабочее, но вовсе не оптимальное и далеко не быстрое. Если представить, что искомое число будет в нижней правой ячейке, то нам придётся перебрать абсолютно все числа, а это целых 30 попыток! При этом мы никак не используем известное нам условие: все числа расположены в порядке возрастания в каждой строке и в каждом столбце.

Следующий вариант решения — использовать 👉 алгоритм бинарного поиска, о котором мы писали ранее. Можно в каждой строке нашей таблицы (или в каждом ряду нашего «стеллажа») пробовать открывать число примерно посередине и отбрасывать варианты слева или справа в зависимости от того, больше или меньше искомое число по значению.

Код решения на «Питоне» будет примерно таким:

def search_value(arr, value):
    if len(arr) == 0 or len(arr[0]) == 0 or not isinstance(value, int):
        return False
    m = len(arr)
    n = len(arr[0])
    for i in range(0, m):
        left = 0
        right = n - 1
        while left <= right:
            middle = round((right - left) / 2) + left
            if arr[i][middle] == value:
                return True
            if arr[i][middle] > value:
                right = middle - 1
            else:
                left = middle + 1
    return False


matrix_arr = [
    [12, 14, 17, 21, 25, 26],
    [13, 15, 18, 22, 29, 32],
    [14, 16, 19, 26, 32, 34],
    [20, 23, 24, 27, 34, 37],
    [28, 31, 33, 36, 40, 46]
]

print(search_value(matrix_arr, 24))  # True

Это решение уже гораздо лучше и быстрее, однако оно учитывает только то, что числа отсортированы по строкам (возрастание слева направо), но не учитывает сортировку по столбцам (возрастание сверху вниз).

Как же тогда учесть сортировку как по строкам, так и по столбцам? Давайте снова взглянем на нашу матрицу a.k.a. таблицу a.k.a. стеллаж:

Предположим, что искомое число находится в самой верхней строке и оно самое большое по значению. Таким образом мы откроем самую правую ячейку с числом 26. Оно больше 24, поэтому смещаемся в наших поисках влево, к меньшему значению.

25 снова больше, а вот 21 уже меньше. Это означает, что мы можем уже перейти на строчку ниже — снова к большему значению, но не проверяя оставшиеся заведомо меньшие значения в первой строке: экономим попытки! 🙂

Мы видим, что 22 меньше искомого числа — смещаться левее в этой строке нет смысла, ведь там тоже будут числа, меньшие искомого. Снова смещаемся на строку вниз: ещё больше экономим попытки и не тыкаемся в ненужные ячейки!

В третьей строке открываем число 26 — оно больше 24, поэтому смещаемся левее и находим 19. Это снова позволяет нам спуститься вниз и вуаля! Мы натыкаемся на искомое значение!

Наглядно наш путь по матрице такой:

Таким образом, мы выполнили поиск практически по диагонали, отбросив множество лишних вариантов! Ну, разве не прекрасно? 🤓

Пример кода решения на языке Python ниже. Это, пожалуй, самый оптимальный и быстрый вариант решения данной задачи:

def search_value(arr, value):
    if len(arr) == 0 or len(arr[0]) == 0 or not isinstance(value, int):
        return False
    m = len(arr)
    n = len(arr[0])
    i = 0
    j = n - 1
    while i < m and j >= 0:
        if arr[i][j] == value:
            return True
        if arr[i][j] > value:
            j -= 1
        else:
            i += 1
    return False


matrix_arr = [
    [12, 14, 17, 21, 25, 26],
    [13, 15, 18, 22, 29, 32],
    [14, 16, 19, 26, 32, 34],
    [20, 23, 24, 27, 34, 37],
    [28, 31, 33, 36, 40, 46]
]

print(search_value(matrix_arr, 24))  # True

Оставить комментарий к этой статье можно в нашем Telegram-канале:

• Telegram

Присоединяйтесь! 😉