Diese Frage hat hier bereits eine Antwort:

Wie suche ich in einem 2D-Array nach einer Zahl, die von links nach rechts und von oben nach unten sortiert ist? 19 Antworten

Angenommen, ich habe eine Matrix (MxN), dessen Zeilen und Spalten sortiert sind.

Alle Elemente in jeder Reihe sind in aufsteigender Reihenfolge angeordnetAlle Elemente in jeder Spalte sind in aufsteigender Reihenfolge angeordnetAlle Elemente sind ganze Zahlen

Andere Annahmen können nicht getroffen werden

Beispiel:

[1 5 8 20]

[2 9 19 21]

[12 15 25 30]

Ich muss herausfinden, ob eine bestimmte Zahl in der Matrix vorhanden ist oder nicht (einfache Suche). Ich habe einen Algorithmus, der läuftO(n)

int row = 0;
int col = N-1;

while (row < M && col >= 0) {
  if (mat[row][col] == elem) { 
    return true;
  } else if (mat[row][col] > elem) { 
    col--;
  } else { 
    row++;
  } 
}

Aber ich wurde gefragtO(log (MxN)) == O(Log(n)) Lösung. Irgendwelche Ideen??