Как эффективно искать в упорядоченной матрице?

Ответ 1

Начните с последнего элемента первой строки (верхний правый угол).
Сравните его с key. У нас есть 3 случая:

• Если они равны, мы закончили.

• Если key больше, чем этот элемент то это означает, что key не может присутствовать в этой строке перемещайте поиск к элементу под ним.

• Если key меньше, чем этот элемент, тогда это означает, что key может присутствовать в этом строка влево и не может присутствовать в столбце дальше вниз, поэтому переместите поиск на элемент слева от него.

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

Псевдокод:

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = C-1

found = false
while( i>=0 && i<R) && (j>=0 && j<C) )
   if (matrix[i][j] == key )
      found = true
      break
   else if( matrix[i][j] > key )
       j--
   else if( matrix[i][j] < key )
       i++
end-while

Ответ 2

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

[Обновление] Для некоторого псевдокода (и обсуждения сложности) см. Ответ Джеффри Л. Уитлеу от этого вопроса.

Ответ 3

// the matrix is like this, from left to right is ascending, and
// from down to up is ascending, but the second row'start is not always bigger than the first row end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/
// 1   5   7    9
// 4   6   10   15
// 8   11  12   19
// 14  16  18   21
// time complexity is O(x+y), x is the count of row, and y is the count of column

public boolean searchMatrix2(int[][] matrix, int target) {
    int rowCount = matrix.length;
    if(rowCount == 0) return false;

    int colCount = matrix[0].length;
    if(colCount == 0) return false;

    //first find the target row, needs O(x)
    int targetRow = 0;
    while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) {
        targetRow++;
    }
    //than find the target in the target row, needs O(y), so the total is O(x)+O(y)
    boolean result = false;
    for(int i = 0; i < colCount; i ++) {
        if(matrix[targetRow][i] == target) {
            result = true;
            break;
        }
    }
    return result;
}

Собственно, мы можем дважды использовать двоичный поиск, сначала найти целевую строку с помощью двоичного поиска, а затем найти цель в строке двоичным поиском, поэтому сложность времени O (lgx) + O (lgy) равна O ( lgx + lgy), лучше O (x + y).