Алгоритм: эффективный способ поиска целого числа в двумерном целочисленном массиве?

Question

Возможные Дубликаты:
Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?
Search a sorted 2D matrix

Время эффективная программа для поиска элемента в двумерной матрице, строки и столбцы которых монотонно возрастает. (Строки и столбцы растут сверху вниз и слева направо).

Я могу думать только о бинарном поиске, если 2D-массив был отсортирован.

Answer 1

Я поставил эту проблему в качестве домашнего задания последнего семестра, и двух студентов, которые я считал, что в среднем, удивил меня, придумывают очень элегантный, простой, и (возможно) оптимального алгоритма:

Find(k, tab, x, y) 
    let m = tab[x][y] 

    if k = m then return "Found" 
    else if k > m then 
    return Find(k, tab, x, y + 1) 
    else 
    return Find(k, tab, x - 1, y) 

Этот алгоритм устраняет либо одну строку, либо один столбец при каждом вызове (обратите внимание, что он является хвостом рекурсивным и может быть преобразован в цикл, тем самым избегая рекурсивных вызовов). Таким образом, если ваша матрица n * m, алгоритм выполняет в O (n + m). Это решение лучше, чем дихотомический поиск, отбрасываемый (что решение я ожидал при раздаче этой проблемы).

EDIT: Я исправил опечатку (к стали х в рекурсивных вызовах), а также, как и Крис отметил, это должно сначала быть вызвано с «верхним правым» углом, то есть Найти (к, вкладки, n, 1), где n - количество строк.

Answer 2

Предполагая, что я правильно прав, вы говорите, что нижняя часть строки n всегда меньше вершины строки n + 1. Если это так, то я бы сказал, что самым простым способом является поиск первой строки с использованием двоичного поиска либо числа, либо следующего наименьшего числа. Затем вы определите столбец, в котором он находится. Затем выполните двоичный поиск этого столбца, пока не найдете его.

Answer 3

Поскольку строки и столбцы монотонно растет, вы можете сделать аккуратную поиска, как это:

Пуск в левом нижнем углу. Если элемент, который вы ищете, больше, чем элемент в этом месте, идите вправо. Если это будет меньше. Повторяйте до тех пор, пока не найдете элемент, или вы не достигли края. Пример (в шестнадцатеричном, чтобы сделать форматирование проще):

1 2 5 6 7 
3 4 6 7 8 
5 7 8 9 A 
7 A C D E 

Давайте искать 8. Начало в позиции (0, 3): 7. 8> 7 поэтому мы идем направо. Сейчас мы находимся в (1, 3): A. 8 < A, поэтому мы идем вверх. На (1, 2): 7, 8> 7, поэтому мы идем направо. (2, 2): 8 -> 8 == 8, поэтому мы закончили.

Вы заметите, однако, что это можно найти только один из элементов, значение 8.

Edit, в случае, если это не было очевидно, это работает в O (N + M) средний и худший время случая.

Answer 4

Начало (0,0)

• в то время как значение слишком низкое, и далее вправо (0,1), то (0,2) и т.д.
• при достижении слишком высокого значения, зайдет одно и оставили один (1,1)

Повторяя эти шаги должны привести вас к цели.