Suche nach einem Element in 2d sortiertem Array in O (log m + log n) Zeit?

Question

Hallo ich wurde in einem Interview zu dieser Frage gefragt. Ich habe nach dem Interview viel gegoogelt, aber ich kann immer noch keine klare Lösung finden. Kann mir jemand sagen, wie ich die (Zeilen-, Spalten-) Paare (ja, gebe zwei Werte zurück) mit der von ihm erwähnten Funktionssignatur zurückgeben kann.

void find(int A[][10], int m, int n, int target, int& row, int& col) 

Answer 1

Ihr Fragetitel unterscheidet sich von der tatsächlichen Frage.so nicht sicher, ob Sie eine Suchmethode verwenden möchten oder wie Sie Werte von dieser Funktionssignatur zurückgeben. So nicht sicher, was genau Sie brauchen und ob das Detail unten korrekt ist oder nicht. Da die beiden Variablen row und col references sind, führen Sie eine Suche durch und füllen Sie die Werte innerhalb der Funktion. Dann können Sie diese beiden Referenzen an der Stelle verwenden, an der Sie anrufen. für zB: wenn Sie die Funktion, wie unten von irgendwo anders nennen:

find(dptr, 5, 19, 5, i,j); 

i und j werden in der funktion bestückt werden Sie sie nach der call.This können implizieren die beiden Werte zurückgegeben wird von die Funktion.

Answer 2

Ich vermute, dass die Matrix auf diese Weise sortiert ist:

1 2 3 
4 5 6 
7 8 9 

zweimal binäre Suchnehmen, beispielsweise Element finden 5:

• die Zeile finden, wo zuerst Spalte < = 5 und zweite Spalte> = 5
• In dieser Zeile finden Sie das Element 5

Binäre Suche ist nur die Methode, das Element in der Mitte auszuwählen. Wenn es zu groß ist, wählen Sie die erste Hälfte, oder wählen Sie die zweite Hälfte. Wiederholen Sie dies, bis Sie das Element gefunden haben, nach dem Sie suchen.