Wie suche ich nach einer Zahl in einem 2d-Array sortiert von links nach rechts und von oben nach unten?

War ich kürzlich dieses interview Frage und ich bin gespannt, was eine gute Lösung wäre.

Sagen, dass ich ein 2d array, wo alle
zahlen im array werden in steigender
Reihenfolge von Links nach rechts und von oben nach
unten.

Was ist der beste Weg zu suchen und zu
bestimmen, ob eine target-Zahl ist in die
array?

Nun, meine erste Neigung ist die Verwendung einer binären Suche, da meine Daten sortiert. Ich kann bestimmen, ob eine Zahl in einer einzigen Zeile in O(log N) Zeit. Allerdings ist es die 2 Richtungen, die werfen mich Weg.

Andere Lösung dachte ich kann die Arbeit beginnen irgendwo in der Mitte. Wenn der mittlere Wert ist kleiner als mein Gegner, dann kann ich sicher sein, dass es in das linke quadratische Teil der matrix aus der Mitte. Ich habe dann Diagonal ziehen und erneut prüfen, die Verringerung der Größe des Quadrats, das Ziel könnte möglicherweise sein, bis ich geschliffen in auf die Ziel-Nummer.

Hat jemand irgendwelche guten Ideen zur Lösung dieses Problems?

Beispiel-array:

Sortiert von Links nach rechts, oben nach unten.

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11

Kommentar zu dem Problem

Einfache Frage: kann es sein, dass Sie haben kann ein Nachbar mit dem gleichen Wert: [[1 1][1 1]] ? Kommentarautor: Matthieu M.

InformationsquelleAutor der Frage Phukab | 2010-03-16

94

Ist hier eine einfache Herangehensweise:
1. Start in der unteren linken Ecke.
2. Wenn das Ziel weniger als diesen Wert, muss er über uns, so um eine.
3. Ansonsten wissen wir, dass das Ziel nicht sein, in dieser Spalte, so rechts verschieben einer.
4. Goto 2.
Für eine NxM array, das läuft in O(N+M). Ich denke, es wäre schwierig, besser zu tun. 🙂

Edit: Viele gute Diskussionen. Ich Sprach über den Allgemeinen Fall oben; klar, wenn N oder M klein sind, könnte man eine binäre Suche Ansatz, dies zu tun in so etwas wie logarithmische Zeit.

Hier sind einige details, für diejenigen, die neugierig sind:

Geschichte

Dieser einfache Algorithmus wird als eine Saddleback Suche. Es ist schon eine Weile herum, und es ist optimal, wenn N == M. Einige Referenzen:
- David Gries, Die Wissenschaft von der Programmierung. Springer-Verlag, 1989.
- Edsgar Dijkstra, Die Saddleback-Suche. Hinweis EWD-934, 1985.
Jedoch, wenn N < M, intuition deutet darauf hin, dass die binäre Suche sollte in der Lage sein, es besser zu machen als O(N+M): Zum Beispiel, wenn N == 1 eine Reine binäre Suche in logarithmischer statt linearer Zeit.

Worst-case-gebunden

Richard Vogel untersucht diese intuition, die binäre Suche verbessern könnte Saddleback-Algorithmus in einer 2006 Papier:
- Richard S. Bird, Die Verbesserung der Saddleback Suche: Eine Lektion in Algorithmus-Design, in Mathematics of Program Construction, S. 82--89, Band 4014, 2006.
Mit einer eher ungewöhnlichen Lehrmethode, Vogel, zeigt uns, dass für N <= M dieses problem eine untere Schranke von Ω(N * log(M/N)). Diese Schranke auch Sinn machen, denn es gibt uns die lineare Leistung, wenn N == M - und logarithmische Leistung, wenn N == 1.

Algorithmen für rechteckige arrays

Einen Ansatz, verwendet eine Zeile-für-Zeile binäre Suche sieht so aus:
1. Beginnen Sie mit einem rechteckigen array, wo N < M. Lassen Sie uns sagen N Zeilen und M ist Spalten.
2. Tun eine binäre Suche in der mittleren Zeile für value. Wenn wir ihn finden, sind wir fertig.
3. Wir sonst gefunden haben, eine benachbarte paar von zahlen s und g, wo s < value < g.
4. Das Rechteck von zahlen oberhalb und Links von s ist weniger als value, so können wir vermeiden es.
5. Das Rechteck unterhalb und rechts von g größer ist als value, so können wir vermeiden es.
6. Gehen Sie zu Schritt (2) für jede der beiden verbleibenden Rechtecke.
In Bezug auf die worst-case Komplexität dieses Algorithmus ist log(M) zu beseitigen Hälfte der möglichen Lösungen, und dann rekursiv ruft sich selbst zweimal auf zwei kleinere Probleme. Wir haben zu wiederholen, eine kleinere version, die log(M) Arbeit für jede Zeile, aber wenn die Anzahl der Zeilen ist klein im Vergleich zu der Anzahl der Spalten, dann in der Lage sein zu beseitigen alle diese Spalten in logarithmischer Zeit beginnt sich lohnt.

Dies gibt der Algorithmus eine Komplexität von T(N,M) = log(M) + 2 * T(M/2, N/2), die Vogel-shows werden O(N * log(M/N)).

Ein weiterer Ansatz, geschrieben von Craig Gidney beschreibt einen Algorithmus ähnlich dem Ansatz vor: er prüft eine Zeile zu einem Zeitpunkt mit einer Schrittweite von M/N. Seine Analyse zeigt, dass diese Ergebnisse in O(N * log(M/N)) Leistung.

Performance-Vergleich

Big-O-Analyse ist ja alles schön und gut, aber wie gut diese Ansätze funktionieren in der Praxis? Das Diagramm unten untersucht vier algorithmen für immer "Platz" - arrays:

(Der "naive" Algorithmus, der einfach durchsucht jedes element des array. Die "rekursiven" Algorithmus, der oben beschrieben ist. Die "hybrid" - Algorithmus ist eine Implementierung von Gidney ' s Algorithmus. Für jede array-Größe, die Leistung wurde gemessen, indem das timing jeder Algorithmus über festen Satz in Höhe von 1.000.000, zufällig generierten arrays.)

Einige Bemerkenswerte Punkte:
- Wie erwartet, die "binary search" - algorithmen bieten die beste Leistung bei den rechteckigen arrays und die Saddleback-Algorithmus funktioniert am besten auf Platz arrays.
- Der Saddleback-Algorithmus führt eine schlechter als die "naive" Algorithmus für die 1-d-arrays, vermutlich, weil es mehrere Vergleiche auf jedes Element.
- Die performance drücken, dass die "binary search" - algorithmen übernehmen quadratischen arrays ist vermutlich aufgrund des Aufwands der Laufenden wiederholte binäre Suche.
Zusammenfassung

Kluge Nutzung der binären Suche kann bieten O(N * log(M/N) Leistung für rechteckige und quadratische arrays. Die O(N + M) "saddleback" - Algorithmus ist viel einfacher, aber leidet unter Leistungsabfall als arrays werden immer rechteckig.

InformationsquelleAutor der Antwort Nate Kohl

Nimmt dieses problem Θ(b lg(t)) Zeit, wo b = min(w,h) und t=b/max(w,h). Ich diskutieren Sie die Lösung in in diesem blog-post.

Untere Schranke

Einen Gegner zwingen kann, einen Algorithmus zu machen Ω(b lg(t)) Abfragen, beschränken sich auf die Hauptdiagonale:

Wie suche ich nach einer Zahl in einem 2d-Array sortiert von links nach rechts und von oben nach unten?

Legende: weisse Zellen sind kleinere Gegenstände, die grauen Zellen sind größere Gegenstände, gelbe Zellen sind kleiner-oder-gleich der Elemente und orange-Zellen sind größer-oder-gleich posten. Der Widersacher Kräfte die Lösung sein, je nachdem, was gelb oder orange Zelle der Algorithmus Abfragen Letzte.

Feststellen, dass es b unabhängige sortierte Listen von Größe t erfordern Ω(b lg(t)) Abfragen vollständig zu eliminieren.

Algorithmus

(Angenommen, ohne Verlust der Allgemeingültigkeit, die w >= h)
Vergleichen Sie die Ziel-item gegen die Zelle t auf der linken Seite der oberen rechten Ecke des gültigen Bereich
- Wenn die Zelle Element passt, zurück die aktuelle position.
- Wenn die Zelle Element kleiner als das Ziel-Element, beseitigen Sie die restlichen t Zellen in der Zeile mit einer binären Suche. Wenn ein passendes Objekt gefunden wird, während dies zu tun, kehren Sie mit Ihrer position.
- Sonst die Zelle, die Sache ist mehr als das Ziel-item, wodurch t kurze Spalten.
, Wenn es keine gültigen Bereich verlassen, Rückkehr scheitern
Goto Schritt 2

Suche nach einem Element:

Wie suche ich nach einer Zahl in einem 2d-Array sortiert von links nach rechts und von oben nach unten?

Bestimmung ein Element nicht existiert:

Wie suche ich nach einer Zahl in einem 2d-Array sortiert von links nach rechts und von oben nach unten?

Legende: weisse Zellen sind kleinere Gegenstände, die grauen Zellen sind größere Gegenstände, und die grüne Zelle ist die gleiche Sache.

Analyse

Gibt es b*t kurze Spalten zu beseitigen. Es gibt b langen Reihen zu beseitigen. Die Beseitigung einer langen Reihe Kosten O(lg(t)) Zeit. Die Beseitigung t kurze Spalten Kosten O(1) Zeit.

Im schlimmsten Fall müssen wir beseitigen, jede Spalte und jede Zeile, die Zeit nehmen O(lg(t)*b + b*t*1/t) = O(b lg(t)).

Beachten Sie, dass ich gehe mal davon aus lg Klemmen, um ein Ergebnis über 1 (d.h. lg(x) = log_2(max(2,x))). Das ist, warum, wenn w=h, Bedeutung t=1 ist, erhalten wir die erwartete Grenze O(b lg(1)) = O(b) = O(w+h).

Code

public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
    if (grid == null) throw new ArgumentNullException("grid");
    comparer = comparer ?? Comparer<T>.Default;

    //check size
    var width = grid.Count;
    if (width == 0) return null;
    var height = grid[0].Count;
    if (height < width) {
        var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
        if (result == null) return null;
        return Tuple.Create(result.Item2, result.Item1);
    }

    //search
    var minCol = 0;
    var maxRow = height - 1;
    var t = height / width;
    while (minCol < width && maxRow >= 0) {
        //query the item in the minimum column, t above the maximum row
        var luckyRow = Math.Max(maxRow - t, 0);
        var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
        if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);

        //did we eliminate t rows from the bottom?
        if (cmpItemVsLucky < 0) {
            maxRow = luckyRow - 1;
            continue;
        }

        //we eliminated most of the current minimum column
        //spend lg(t) time eliminating rest of column
        var minRowInCol = luckyRow + 1;
        var maxRowInCol = maxRow;
        while (minRowInCol <= maxRowInCol) {
            var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
            var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
            if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
            if (cmpItemVsMid > 0) {
                minRowInCol = mid + 1;
            } else {
                maxRowInCol = mid - 1;
                maxRow = mid - 1;
            }
        }

        minCol += 1;
    }

    return null;
}

InformationsquelleAutor der Antwort Craig Gidney

17

Ich würde verwenden Sie die divide-und-conquer-Strategie für dieses problem, ähnlich zu dem, was Sie vorgeschlagen, aber die details sind ein bisschen anders.

Dies wird eine rekursive Suche auf Teilbereiche der matrix.

Bei jedem Schritt, wählen Sie ein element in der Mitte der Reihe. Wenn der Wert gefunden ist, was Sie suchen, dann sind Sie fertig.

Andernfalls, wenn der Wert kleiner ist als der Wert, den Sie suchen, dann wissen Sie, dass es nicht im Quadranten oben und Links von der aktuellen position. So rekursiv suchen die beiden Teilbereiche: alles (ausschließlich) unterhalb der aktuellen position, und alles (ausschließlich) auf das Recht, auf oder oberhalb der aktuellen position.

Andernfalls (der Wert ist größer als der Wert, den Sie suchen) Sie wissen, dass es nicht im Quadranten unterhalb und rechts von Ihrer aktuellen position. So rekursiv suchen die beiden Teilbereiche: alles (ausschließlich) Links von der aktuellen position, und alles (ausschließlich) über die aktuelle position, die ist auf der aktuellen Spalte oder eine Spalte nach rechts.

Ba-da-bing, fand Sie es.

Beachten Sie, dass jeder rekursive Aufruf befasst sich nur mit den aktuellen Teilbereich, nicht (zum Beispiel) ALLE Zeilen oberhalb der aktuellen position. Nur die in der aktuellen Teilbereich.

Hier einige pseudocode für Sie:
```
bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)

if (minX == maxX and minY == maxY and arr[minX,minY] != value)
    return false
if (arr[minX,minY] > value) return false;  //Early exits if the value can't be in 
if (arr[maxX,maxY] < value) return false;  //this subrange at all.
int nextX = (minX + maxX) /2
int nextY = (minY + maxY) /2
if (arr[nextX,nextY] == value)
{
    print nextX,nextY
    return true
}
else if (arr[nextX,nextY] < value)
{
    if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
        return true
    return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
    if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
        return true
    reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}
```
InformationsquelleAutor der Antwort Jeffrey L Whitledge

Die zwei wichtigsten Antworten geben, so weit scheinen die wohl O(log N) "Zick-Zack-Methode" und die O(N+M) Binary-Search-Methode. Ich dachte, ich würde tun einige Tests zum Vergleich der beiden Methoden mit einigen verschiedenen setups. Hier sind die details:

Array N x N-Quadrat in jedem test, mit N variieren von 125 bis 8000 (die größte meiner JVM-heap behandeln konnte). Für jede array-Größe, nahm ich eine zufällige Stelle im array ein einziges 2. Dann legte ich eine 3 überall möglich (rechts und unten von 2) und füllten dann den rest des Arrays mit 1. Einige der früheren Kommentatoren schien zu denken, diese Art der Installation würde die Ausbeute worst-case Laufzeit für beide algorithmen. Für jedes array-Größe", ich nahm 100 verschiedenen zufälligen Orten für die 2 (search target) und lief der test. Ich nahm avg Laufzeit und worst-case Laufzeit für jeden Algorithmus. Da war es passiert zu schnell zu gute ms-Messungen in Java, und weil ich nicht Vertrauen Java nanoTime(), wiederholte ich jeden test 1000 mal nur um ein uniform bias-Faktor, zu allen Zeiten. Hier sind die Ergebnisse:

Wie suche ich nach einer Zahl in einem 2d-Array sortiert von links nach rechts und von oben nach unten?

Zick-Zack-beat binary in jedem test für beide avg und worst-case Zeiten, aber Sie sind alle in einer Größenordnung von einander mehr oder weniger.

Hier ist der Java code:

public class SearchSortedArray2D {

    static boolean findZigZag(int[][] a, int t) {
        int i = 0;
        int j = a.length - 1;
        while (i <= a.length - 1 && j >= 0) {
            if (a[i][j] == t) return true;
            else if (a[i][j] < t) i++;
            else j--;
        }
        return false;
    }

    static boolean findBinarySearch(int[][] a, int t) {
        return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
    }

    static boolean findBinarySearch(int[][] a, int t,
            int r1, int c1, int r2, int c2) {
        if (r1 > r2 || c1 > c2) return false; 
        if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
        if (a[r1][c1] > t) return false;
        if (a[r2][c2] < t) return false;

        int rm = (r1 + r2) / 2;
        int cm = (c1 + c2) / 2;
        if (a[rm][cm] == t) return true;
        else if (a[rm][cm] > t) {
            boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
            boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
            return (b1 || b2);
        } else {
            boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
            boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
            return (b1 || b2);
        }
    }

    static void randomizeArray(int[][] a, int N) {
        int ri = (int) (Math.random() * N);
        int rj = (int) (Math.random() * N);
        a[ri][rj] = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == ri && j == rj) continue;
                else if (i > ri || j > rj) a[i][j] = 3;
                else a[i][j] = 1;
            }
        }
    }

    public static void main(String[] args) {

        int N = 8000;
        int[][] a = new int[N][N];
        int randoms = 100;
        int repeats = 1000;

        long start, end, duration;
        long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
        long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
        long zigSum = 0, zigAvg;
        long binSum = 0, binAvg;

        for (int k = 0; k < randoms; k++) {
            randomizeArray(a, N);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findZigZag(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            zigSum += duration;
            zigMin = Math.min(zigMin, duration);
            zigMax = Math.max(zigMax, duration);

            start = System.currentTimeMillis();
            for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
            end = System.currentTimeMillis();
            duration = end - start;
            binSum += duration;
            binMin = Math.min(binMin, duration);
            binMax = Math.max(binMax, duration);
        }
        zigAvg = zigSum / randoms;
        binAvg = binSum / randoms;

        System.out.println(findZigZag(a, 2) ?
                "Found via zigzag method. " : "ERROR. ");
        //System.out.println("min search time: " + zigMin + "ms");
        System.out.println("max search time: " + zigMax + "ms");
        System.out.println("avg search time: " + zigAvg + "ms");

        System.out.println();

        System.out.println(findBinarySearch(a, 2) ?
                "Found via binary search method. " : "ERROR. ");
        //System.out.println("min search time: " + binMin + "ms");
        System.out.println("max search time: " + binMax + "ms");
        System.out.println("avg search time: " + binAvg + "ms");
    }
}

InformationsquelleAutor der Antwort The111

5

Dies ist ein kurzer Beweis der unteren Schranke für das problem.

Können Sie nicht besser als die lineare Zeit (in Bezug auf die Dimensionen des Arrays, nicht die Anzahl der Elemente). Im unteren Bereich jedes der Elemente, gekennzeichnet als * können entweder 5 oder 6 (unabhängig von anderen). Also, wenn Ihr Ziel nicht Wert ist 6 (oder 5) muss der Algorithmus überprüfen Sie alle von Ihnen.
```
1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10
```
Natürlich erweitert, um größere arrays. Dies bedeutet, dass diese Antwort optimal ist.

Update: Wie bereits von Jeffrey L Whitledge, es ist nur optimal, wie die asymptotische untere Schranke für die Laufzeit vs input-Daten Größe (behandelt als eine einzelne variable). Laufzeit als zwei-Variablen-Funktion auf beiden array-Dimensionen verbessert werden kann.

InformationsquelleAutor der Antwort Rafał Dowgird

Ich denke, Hier ist die Antwort und es funktioniert für jede Art der sortierten matrix

bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
    if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
    if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
    if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
    if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;

    int xnew = (xmin + xmax)/2;
    int ynew = (ymin + ymax)/2;

    if (arr[xnew][ynew] == key) return true;
    if (arr[xnew][ynew] < key)
    {
        if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
    } else {
        if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
            return true;
        return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
    }
}

InformationsquelleAutor der Antwort Sridhar Ravipati

1

Interessante Frage. Betrachten Sie diese Idee - erstellen Sie eine Grenze, wo alle zahlen, die größer sind als Ihre Zielgruppe und anderen, wo alle zahlen sind kleiner als Ihre Gegner. Wenn etwas übrig ist, zwischen den beiden, das ist Ihr Ziel.

Wenn ich mich für 3 in deinem Beispiel, ich Lesen Sie über die erste Zeile, bis ich die Treffer 4, dann für die kleinste benachbarte Zahl (einschließlich der diagonalen) größer als 3:

1 2 4 5 6

2 3 5 7 8

4 6 8 9 10

5 8 9 10 11

Nun Tue ich das gleiche für diejenigen, die zahlen weniger als 3:

1 2 4 5 6

2 3 5 7 8

4 6 8 9 10

5 8 9 10 11

Nun Frage ich, ist alles, was in den beiden Grenzen? Wenn ja, es müssen 3 sein. Wenn Nein, dann gibt es keine 3. Art der indirekten, da ich eigentlich gar nicht finden, die Anzahl, die ich nur folgern, dass es vorhanden sein muss. Dies hat den zusätzlichen bonus von zählen ALLE 3.

Ich versuchte dies auf einige Beispiele, und es scheint zu funktionieren OK.

InformationsquelleAutor der Antwort Grembo
1

Binäre Suche durch die Diagonale des Arrays ist die beste option.
Wir finden heraus, ob das element kleiner oder gleich den Elementen in der diagonalen.

InformationsquelleAutor der Antwort Nikhil K R
0

A. Tun, eine binäre Suche auf den Zeilen, in denen die Ziel-Nummer auf sein.

B. Machen Sie ein Diagramm : achten Sie auf die Anzahl von nehmen immer die kleinste unbesuchte Nachbar-Knoten und backtracking, wenn ein zu großer Anzahl gefunden wird

InformationsquelleAutor der Antwort Tuomas Pelkonen
0

Binäre Suche wäre die beste Lösung, imo. Ab 1/2-x, 1/2-y, wird es in die Hälfte geschnitten. DH ein 5x5 Quadrat wäre so etwas wie x == 2 /y == 3 . Abgerundet ich einen Wert nach unten und ein Wert von bis zu besseren zone in der Richtung des angestrebten Wert.

Für Klarheit die nächste iteration geben würde, Sie so etwas wie x == 1 /y == 2 ODER x == 3 /y == 5

InformationsquelleAutor der Antwort Woot4Moo
0

Nun, um zu beginnen, lassen Sie uns annehmen, wir sind mit einem Quadrat.
```
1 2 3
2 3 4
3 4 5
```
1. Suche einen Platz

Ich würde verwenden eine binäre Suche auf der diagonalen. Das Ziel ist, suchen Sie die kleinere Zahl, dass ist nicht unbedingt niedriger als die Ziel-Nummer.

Sagen, ich bin auf der Suche nach 4 zum Beispiel, dann würde ich am Ende der Lokalisierung 5 bei (2,2).

Dann, ich bin sicher, dass, wenn 4 ist in der Tabelle, es ist an einer position entweder (x,2) oder (2,x) mit x im [0,2]. Gut, das ist nur 2 binäre Suche.

Die Komplexität nicht abschreckend: O(log(N)) (3 binäre Suche auf Bereiche von Länge N)

2. Suche ein Rechteck, ein naiver Ansatz

Natürlich wird das ein bisschen komplizierter, wenn N und M unterscheiden sich (mit einem Rechteck), sollten Sie diese entarteten Fall:
```
1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
```
Und sagen wir, ich bin auf der Suche nach 9... Der Diagonale Ansatz ist immer noch gut, aber die definition der diagonalen ändert. Hier meine Diagonale ist [1, (5 or 6), 17]. Sagen wir, ich nahm [1,5,17], dann weiß ich, dass wenn 9 ist in der Tabelle ist es entweder in den Abschnitt:
```
            5  6  7  8
            6  7  8  9
10 11 12 13 14 15 16
```
Dies gibt uns 2 Rechtecke:
```
5 6 7 8    10 11 12 13 14 15 16
6 7 8 9
```
So können wir recurse! wahrscheinlich Anfang durch die man mit weniger Elementen (obwohl in diesem Fall es tötet uns).

Ich soll zeigen, dass, wenn eine der Dimensionen ist weniger als 3 können wir nicht gelten die Diagonale Methoden und verwenden müssen, eine binäre Suche. Hier würde es bedeuten:
- Anwenden binäre Suche auf 10 11 12 13 14 15 16 nicht gefunden
- Anwenden binäre Suche auf 5 6 7 8 nicht gefunden
- Anwenden binäre Suche auf 6 7 8 9 nicht gefunden
Es ist schwierig, weil man eine gute Leistung, die Sie wollen könnten, zu unterscheiden zwischen mehreren Fällen, abhängig von der Allgemeinen Form....

3. Suche ein Rechteck, das brutale Vorgehen

Es wäre viel einfacher, wenn wir befassten uns mit einem Quadrat... also lasst uns einfach Platz machen.
```
1  2  3  4  5  6  7  8
2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17
17 .  .  .  .  .  .  17
.                    .
.                    .
.                    .
17 .  .  .  .  .  .  17
```
Wir haben jetzt ein Quadrat.

Natürlich werden wir wohl NICHT wirklich schaffen, diese Zeilen könnten wir einfach nacheifern.
```
def get(x,y):
  if x < N and y < M: return table[x][y]
  else: return table[N-1][M-1]            # the max
```
also es verhält sich wie ein Quadrat ohne Besatzungsmacht mehr Speicher (auf Kosten der Geschwindigkeit, wahrscheinlich, je nach cache... naja :p)

InformationsquelleAutor der Antwort Matthieu M.
0

EDIT:

Ich falsch verstanden, die Frage. Wie die Kommentare zeigen dies funktioniert nur in den engeren Fall.

In einer Sprache wie C, die speichert die Daten im row-major order, einfach behandeln es als ein 1D-array der Größe n * m und verwenden eine binäre Suche.

InformationsquelleAutor der Antwort Hugh Brackett
0

Ich habe einen rekursiven Divide & Conquer-Lösung.
Grundlegende Idee für ein Schritt ist: Wir wissen, dass der Linken-Oberen(LU) ist die kleinste und die rechts unten(RB) ist der größte Nr. also das da Keine(N) muss: N>=LU und N<=RB

WENN N== - LU und N==RB::::Element Gefunden und Abbruch der Rückkehr die position/Index
Wenn N>=LU und N<=RB = FALSE, Nein ist es nicht und bricht ab.
Wenn N>=LU und N<=RB = TRUE, Teilen Sie das 2D-array in 4 gleiche Teile des 2D-array jeweils in logischer Weise..
Und dann gelten die gleichen algo Schritt für alle vier sub-array.

Mein Algo ist Richtig implementierte ich auf meinem PC Freunde.
Komplexität: je 4 Vergleiche b verwendet, um Rückschlüsse auf die Gesamtzahl der Elemente auf ein Viertel im schlimmsten Fall..
Also Mein Komplexität kommt auf 1 + 4 x lg(n) + 4
Aber wirklich erwartet, dass dies auf O(n)

Ich denke, etwas ist falsch irgendwo in meiner Berechnung der Komplexität, bitte korrigieren wenn dem so ist..

InformationsquelleAutor der Antwort Pervez Alam
0

Die optimale Lösung ist, um zu beginnen in der oberen linken Ecke,, die hat einen minimalen Wert. Verschieben Diagonal nach unten rechts, bis Sie auf ein element, dessen Wert >= Wert des Elements. Wenn das element Wert ist gleich dem Wert des angegebenen Elements zurück gefunden, wie wahr.

Ansonsten, von hier aus können wir gehen, gibt es zwei Möglichkeiten.

Strategie 1:
1. Nach oben in die Spalte und suchen Sie das element, bis wir das Ende erreichen. Wenn gefunden, Rückkehr fand als wahr
2. Verschieben nach Links in der Zeile, und suchen Sie das element, bis wir das Ende erreichen. Wenn gefunden, Rückkehr fand als wahr
3. Rückkehr fand als falsch
Strategie 2:
Lasse ich die Bezeichnung der Zeilenindex und j bezeichnen die Spalte index der Diagonale element, das wir aufgehört haben. (Hier haben wir i = j, BTW). Let k = 1.
- Wiederhole die folgenden Schritte bis zur i-k >= 0
  1. Der Suche, wenn a[i-k][j] ist gleich dem angegebenen element. wenn ja, zurück gefunden, wie wahr.
  2. Der Suche, wenn a[i][j-k] ist gleich dem angegebenen element. wenn ja, zurück gefunden, wie wahr.
  3. Schrittweite k
1 2 4 5 6

2 3 5 7 8

4 6 8 9 10

5 8 9 10 11

InformationsquelleAutor der Antwort Murali Mohan

public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){

    //base case for recursion
    if(minX > maxX || minY > maxY)
        return false ;
    //early fails
    //array not properly intialized
    if(arr==null || arr.length==0)
        return false ;
    //arr[0][0]> key return false
    if(arr[minX][minY]>key)
        return false ;
    //arr[maxX][maxY]<key return false
    if(arr[maxX][maxY]<key)
        return false ;
    //int temp1 = minX ;
    //int temp2 = minY ;
    int midX = (minX+maxX)/2 ;
    //if(temp1==midX){midX+=1 ;}
    int midY = (minY+maxY)/2 ;
    //if(temp2==midY){midY+=1 ;}


    //arr[midX][midY] = key ? then value found
    if(arr[midX][midY] == key)
        return true ;
    //alas ! i have to keep looking

    //arr[midX][midY] < key ? search right quad and bottom matrix ;
    if(arr[midX][midY] < key){
        if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
            return true ;
        //search bottom half of matrix
        if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
            return true ;
    }
    //arr[midX][midY] > key ? search left quad matrix ;
    else {
         return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
    }
    return false ;

}

InformationsquelleAutor der Antwort gsb

0

Schlage ich vor, speichern Sie alle Zeichen in einem 2D list. dann finden Sie den index des gewünschten Elements, wenn es vorhanden ist in der Liste.

Wenn nicht Druck auf die entsprechende Meldung else print (Zeile und Spalte) als:

row = (index/total_columns) und column = (index%total_columns -1)

Fällt nur die binäre Suche Zeit in einer Liste.

Bitte machen Sie eventuelle Korrekturen. 🙂

InformationsquelleAutor der Antwort Abhi31jeet

Wenn O(M log(N)) Lösung ist ok für eine MxN-array -

template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
  struct MN *result = new MN;
  result->m = -1;
  result->n = -1;

  /* Do a binary search on each row since rows (and columns too) are sorted. */
  for(int i = 0; i < M; i++){
    int lo = 0; int hi = N - 1;
    while(lo <= hi){
      int mid = lo + (hi-lo)/2;
      if(k < a[i][mid]) hi = mid - 1;
      else if (k > a[i][mid]) lo = mid + 1;
      else{
        result->m = i;
        result->n = mid;
        return result;
      }
    }
  }
  return result;
}

C++ demo.

Bitte lassen Sie mich wissen, wenn dies nicht funktionieren würde, oder wenn es ein bug ist es.

InformationsquelleAutor der Antwort kaushal

-1

Gegeben eine quadratische matrix wie folgt:
```
[ a b c ] 
[ d e f ] 
[ i j k ] 
```
Wissen wir, dass ein < c, d < f i < k. Was wir nicht wissen, ist, ob d < c oder d - > c usw.. Wir haben garantiert nur in 1 dimension.

Blick auf die end-Elemente (c,f,k), wir können eine Art von filter: ist N < c ? search() : next(). Damit haben wir n Iterationen über die Zeilen, wobei jede Zeile der Einnahme von entweder O( log( n ) ) binäre Suche oder O( 1 ) wird gefiltert.

Lassen Sie mich ein BEISPIEL gegeben, wobei N = j,

1) Überprüfen Sie Zeile 1. j < c? (Nein, gehen Sie weiter)

2) markieren Sie die Zeile 2. j < f? (ja, bin Suche wird nichts)

3) Überprüfen Sie die Zeile 3. j < k? (ja, bin Suche findet es)

Versuchen Sie es erneut mit N = q,

1) Überprüfen Sie Zeile 1. q < c? (Nein, gehen Sie weiter)

2) markieren Sie die Zeile 2. q < f? (Nein, gehen Sie weiter)

3) Überprüfen Sie die Zeile 3. q < k? (Nein, gehen Sie weiter)

Es gibt vermutlich eine bessere Lösung gibt, aber das ist einfach zu erklären.. 🙂

InformationsquelleAutor der Antwort apandit
-4

Da dieses eine interview-Frage, es würde scheinen, führen zu einer Diskussion der Parallele Programmierung und Map-reduce algorithmen.

Sehen http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html

InformationsquelleAutor der Antwort GarethOwen

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

Geschichte

Worst-case-gebunden

Algorithmen für rechteckige arrays

Performance-Vergleich

Zusammenfassung