Effiziente Möglichkeit, ein Element zu suchen

88

Kürzlich hatte ich ein Interview, in dem sie mir eine " Suchfrage " stellten.
Die Frage war:

Angenommen, es gibt ein Array von (positiven) Ganzzahlen, von denen jedes Element entweder ist +1oder -1mit seinen benachbarten Elementen verglichen wird.

Beispiel:

array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

Suchen Sie nun nach 7seiner Position und geben Sie sie zurück.

Ich gab diese Antwort:

Speichern Sie die Werte in einem temporären Array, sortieren Sie sie und wenden Sie dann die binäre Suche an.

Wenn das Element gefunden wird, geben Sie seine Position im temporären Array zurück.
(Wenn die Zahl zweimal vorkommt, geben Sie ihr erstes Vorkommen zurück.)

Aber sie schienen mit dieser Antwort nicht zufrieden zu sein.

Was ist die richtige Antwort?

NSUser
quelle
4
Soweit ich weiß, ist eine lineare Suche eine gute Möglichkeit, den Index eines Elements im Array zu lokalisieren. Ich bin mir noch nicht sicher, welchen anderen Suchalgorithmus der Index eines Elements effizient lokalisieren kann.
Sean Francis N. Ballais
4
Wenn 7 garantiert nur einmal erscheint oder wenn es keine Rolle spielt, welche 7 zurückgegeben wird, können Sie den linearen Algorithmus der Antwort von Coleman weiter verbessern.
user1942027
52
Wenn Ihre ursprüngliche Lösung sortiert werden muss, ist sie schlechter als die naive lineare Suche. Sie scheinen sich dessen nicht bewusst zu sein.
cubuspl42
5
Das Sortieren erfordert O (nlogn) und eine binäre Suche ist O (logn). Wenn Sie viele, viele Werte aus dem großen Array suchen müssen, ist Ihre Antwort möglicherweise besser. Wenn Sie jedoch nur einmal suchen, sind O (n) -Algorithmen möglicherweise besser.
Jingyu9575
23
Ich weiß nicht, warum niemand anderes dies erwähnt hat: Ihre Methode war nicht nur ineffizient, sie war auch falsch , und das ist viel schlimmer als bloße Ineffizienz. Voraussetzung ist die Position einer bestimmten Zahl im ursprünglichen Array . Ihre Methode gibt die Position der Nummer in einem sortierten Array zurück . Nun, man könnte die ursprüngliche Position abrufen, durch die einfache Anordnung Umwandlung in ein Array von Tupeln (Anzahl, orig_pos) vor dem Sortieren. Aber das hast du nicht erwähnt, also hast du es wohl auch im Interview nicht erwähnt.
Tom Zych

Antworten:

126

Sie können eine lineare Suche mit Schritten durchführen, die häufig größer als 1 sind. Die entscheidende Beobachtung ist, dass, wenn z. B. array[i] == 4und 7 noch nicht erschienen sind, der nächste Kandidat für 7 im Index ist i+3. Verwenden Sie eine while-Schleife, die wiederholt direkt zum nächsten geeigneten Kandidaten führt.

Hier ist eine leicht verallgemeinerte Implementierung. Es findet das erste Auftreten kim Array (vorbehaltlich der Einschränkung + = 1) oder -1wenn es nicht auftritt:

#include <stdio.h>
#include <stdlib.h>

int first_occurence(int k, int array[], int n);

int main(void){
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
    printf("7 first occurs at index %d\n",first_occurence(7,a,15));
    printf("but 9 first \"occurs\" at index %d\n",first_occurence(9,a,15));
    return 0;
}

int first_occurence(int k, int array[], int n){
    int i = 0;
    while(i < n){
        if(array[i] == k) return i;
        i += abs(k-array[i]);
    }
    return -1;
}

Ausgabe:

7 first occurs at index 11
but 9 first "occurs" at index -1
John Coleman
quelle
8
Genau das, was ich dachte. Dies ist O(N), aber ich glaube nicht, dass es einen schnelleren Weg gibt, dies zu tun.
Shapiro Yaacov
2
Sie könnten es im Durchschnitt mit mehr Kandidaten (z. B. erstem und letztem) etwas schneller machen und dann mit demjenigen gehen, der dem Ziel am nächsten ist - wenn Sie nur ein einziges Vorkommen finden müssen, nicht das erste.
mkadunc
2
@mkadunc Das ist eine gute Idee. Eine andere Beobachtung ist, dass, wenn das erste und das letzte Element 7 überspannen, Sie in diesem speziellen Fall eine binäre Suche verwenden können (wenn es Ihnen egal ist, welche 7 Sie finden)
John Coleman
1
Für den Fall, dass Sie eine 7 finden müssen (nicht unbedingt die erste), schlage ich die folgende (praktische) Verbesserung vor. Erstellen Sie eine Liste mit Abschnitten (zwei Ganzzahlen, 'Start' und 'Ende') und beginnen Sie in der Mitte, anstatt am Anfang des Arrays zu beginnen. Ignorieren Sie entsprechend dem Wert in der Zelle den relevanten Bereich und fügen Sie die beiden verbleibenden Abschnitte zu Ihrer Liste der Abschnitte hinzu. Wiederholen Sie nun für das nächste Element in der Liste. Dies ist immer noch 'O (n)', aber Sie ignorieren den doppelten Bereich jedes Mal, wenn Sie eine Zelle überprüfen.
Shapiro Yaacov
3
@ShapiroYaacov: In Kombination mit der Überprüfung, ob das Intervall vom unteren zum höheren Wert auf beiden Seiten eines Abschnitts k (7) enthält, verdient dies eine eigene Antwort.
Graubart
35

Ihr Ansatz ist zu kompliziert. Sie müssen nicht jedes Array-Element untersuchen. Der erste Wert ist 4, also 7sind zumindest 7-4 Elemente entfernt, und Sie können diese überspringen.

#include <stdio.h>
#include <stdlib.h>

int main (void)
{
    int array[] = {4,5,6,5,4,3,2,3,4,5,6,7,8};
    int len = sizeof array / sizeof array[0];
    int i = 0;
    int steps = 0;
    while (i < len && array[i] != 7) {
        i += abs(7 - array[i]);
        steps++;
    }

    printf("Steps %d, index %d\n", steps, i);
    return 0;
}

Programmausgabe:

Steps 4, index 11

Bearbeiten: verbessert nach Kommentaren von @Raphael Miedl und @Martin Zabel.

Wetterfahne
quelle
2
Ein Nitpick if ((skip = 7 - array[i]) < 1) skip = 1;scheint es meiner Meinung nach zu komplizieren und zu pessimieren. Wenn array[i] == 200Sie -193jedes Mal um 1 kommen und einfach überspringen, obwohl Sie alle 193 überspringen könnten. Warum nicht einfach i += abs(7 - array[i])?
user1942027
1
Sie sollten skipdie absolute Differenz zwischen 7 und einstellen array[i].
Martin Zabel
@ Raphael Miedl nein, ein Element wird nicht sein 200, du hättest bestanden 7.
Wetterfahne
3
@WeatherVane haben wir diese Garantie nicht, nur dass benachbarte Werte +1/ -1voneinander sind. So könnte es einfach sein array[0] == 200und die anderen sind meistens -1.
user1942027
1
@WeatherVane Dies setzt voraus, dass das Element immer im Array gefunden wird, was möglicherweise nicht der Fall ist. -1 ist in diesem Fall eine gültige Rückgabe; was den Code ändert, den Sie ziemlich haben
Eugene
20

Eine Variation der herkömmlichen linearen Suche könnte ein guter Weg sein. Lassen Sie uns ein Element auswählen, sagen wir array[i] = 2. Jetzt ist array[i + 1]entweder 1 oder 3 (ungerade), array[i + 2]ist (nur positive ganze Zahlen) 2 oder 4 (gerade Zahl).

Wenn Sie so weitermachen, ist ein Muster zu beobachten - array[i + 2*n]es enthält gerade Zahlen, sodass alle diese Indizes ignoriert werden können.

Das können wir auch sehen

array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7

Daher i + 5sollte der Index als nächstes überprüft werden, und eine while-Schleife kann verwendet werden, um den nächsten zu überprüfenden Index zu bestimmen, abhängig von dem am Index gefundenen Wert i + 5.

Dies hat zwar Komplexität O(n)(lineare Zeit in Bezug auf asymptotische Komplexität), ist jedoch in praktischer Hinsicht besser als eine normale lineare Suche, da nicht alle Indizes besucht werden.

Offensichtlich wird all dies umgekehrt, wenn array[i](unser Ausgangspunkt) ungerade war.

Madhav Datt
quelle
8

Der von John Coleman vorgestellte Ansatz ist höchstwahrscheinlich der, auf den der Interviewer gehofft hat.
Wenn Sie bereit sind, etwas komplizierter zu werden, können Sie die erwartete Sprunglänge erhöhen:
Rufen Sie den Zielwert k auf . Beginnen Sie mit dem Wert v des ersten Elements an Position p und nennen Sie die Differenz kv dv mit dem Absolutwert av . Um negative Suchvorgänge zu beschleunigen, werfen Sie einen Blick auf das letzte Element als den anderen Wert u an Position o: Wenn dv × du negativ ist, ist k vorhanden (wenn ein Auftreten von k akzeptabel ist, können Sie den Indexbereich hier wie bei der binären Suche eingrenzen). Wenn av + au größer als die Länge des Arrays ist, fehlt k. (Wenn dv × du Null ist, ist v oder u gleich k.)
Auslassen der Indexgültigkeit: Prüfen Sie die ("nächste") Position, an der die Sequenz mit k in der Mitte zu v zurückkehren könnte : o = p + 2*av.
Wenn dv × du negativ ist, finde k (rekursiv?) Von p + av bis o-au;
Wenn es Null ist, ist u gleich k bei o.
Wenn ich gleich dv und der Wert in der Mitte ist nicht k oder au überschreitet av,
oder Sie scheitern k von p zu finden + av o-au,
lassen p=o; dv=du; av=au;und halten Sondieren.
(Für einen vollständigen Rückblick auf die Texte der 60er Jahre mit Courier anzeigen. Mein "1. 2. Gedanke" war zu verwendeno = p + 2*av - 1, was du gleich dv ausschließt .)

Graubart
quelle
3

SCHRITT 1

Beginnen Sie mit dem ersten Element und prüfen Sie, ob es 7 ist. Angenommen, es chandelt sich um den Index der aktuellen Position. Also zunächst c = 0.

SCHRITT 2

Wenn es 7 ist, haben Sie den Index gefunden. Es ist c. Wenn Sie das Ende des Arrays erreicht haben, brechen Sie aus.

SCHRITT 3

Wenn dies nicht der Fall ist, müssen 7 mindestens |array[c]-7|Positionen entfernt sein, da Sie nur eine Einheit pro Index hinzufügen können. Fügen |array[c]-7|Sie daher zu Ihrem aktuellen Index c hinzu, und gehen Sie erneut zu SCHRITT 2, um dies zu überprüfen.

Im schlimmsten Fall, wenn es abwechselnd 1 und -1 gibt, kann die Zeitkomplexität O (n) erreichen, aber durchschnittliche Fälle würden schnell geliefert.

Akeshwar Jha
quelle
Wie unterscheidet sich das von John Colemans Antwort? (Abgesehen davon, dass vorgeschlagen wird, |c-7|wo dies |array[c]-7|
erforderlich
Ich habe gerade seine Antwort gesehen. Ich gebe zu, dass die Kernidee dieselbe ist.
Akeshwar Jha
Die ursprüngliche Frage besagt nicht, dass das Array mit einer Zahl kleiner als 7 beginnt. Es array[c]-7kann also positiv oder negativ sein. Sie müssen sich abs()vor dem Vorwärtsspringen darauf bewerben .
Arielf
Ja, du hast Recht. Deshalb verwende ich array[c] - 7mit dem Modul-Operator |array[c] - 7|.
Akeshwar Jha
3

Hier gebe ich die Implementierung in Java ...

public static void main(String[] args) 
{       
    int arr[]={4,5,6,5,4,3,2,3,4,5,6,7,8};
    int pos=searchArray(arr,7);

    if(pos==-1)
        System.out.println("not found");
    else
        System.out.println("position="+pos);            
}

public static int searchArray(int[] array,int value)
{
    int i=0;
    int strtValue=0;
    int pos=-1;

    while(i<array.length)
    {
        strtValue=array[i];

        if(strtValue<value)
        {
            i+=value-strtValue;
        }
        else if (strtValue==value)
        {
            pos=i;
            break;
        }
        else
        {
            i=i+(strtValue-value);
        }       
    }

    return pos;
}
kaushik
quelle
2
Undokumentierter Code in einer Sprache mit einer mindestens halboffiziellen Konvention . Wie unterscheidet sich dies von den Antworten von John Coleman und Akeshwar, außer dass das Tag "c" großzügig interpretiert wird?
Graubart
3

Hier ist eine Lösung im Divide-and-Conquer-Stil. Auf Kosten von (viel) mehr Buchhaltung können wir mehr Elemente überspringen; Anstatt von links nach rechts zu scannen, testen Sie in der Mitte und überspringen Sie in beide Richtungen.

#include <stdio.h>                                                               
#include <math.h>                                                                

int could_contain(int k, int left, int right, int width);                        
int find(int k, int array[], int lower, int upper);   

int main(void){                                                                  
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};                                   
    printf("7 first occurs at index %d\n",find(7,a,0,14));                       
    printf("but 9 first \"occurs\" at index %d\n",find(9,a,0,14));               
    return 0;                                                                    
}                                                                                

int could_contain(int k, int left, int right, int width){                        
  return (width >= 0) &&                                                         
         (left <= k && k <= right) ||                                            
         (right <= k && k <= left) ||                                            
         (abs(k - left) + abs(k - right) < width);                               
}                                                                                

int find(int k, int array[], int lower, int upper){                              
  //printf("%d\t%d\n", lower, upper);                                            

  if( !could_contain(k, array[lower], array[upper], upper - lower )) return -1;  

  int mid = (upper + lower) / 2;                                                 

  if(array[mid] == k) return mid;                                                

  lower = find(k, array, lower + abs(k - array[lower]), mid - abs(k - array[mid]));
  if(lower >= 0 ) return lower;                                                    

  upper = find(k, array, mid + abs(k - array[mid]), upper - abs(k - array[upper]));
  if(upper >= 0 ) return upper;                                                  

  return -1;                                                                     

}
Neal Fultz
quelle
neal-fultz Ihre Antwort gibt nicht das erste Vorkommen zurück, sondern jedes zufällige Vorkommen des Suchelements, wenn Sie von der Mitte aus beginnen und von beiden Seiten überspringen.
Ram Patra
Das Umschalten der Rekursionsreihenfolge bleibt dem Leser als Übung überlassen.
Neal Fultz
1
neal-fultz dann bearbeiten Sie bitte die Nachricht in Ihrem printf () -Methodenaufruf.
Ram Patra
1

const findMeAnElementsFunkyArray = (arr, ele, i) => {
  const elementAtCurrentIndex = arr[i];

  const differenceBetweenEleAndEleAtIndex = Math.abs(
    ele - elementAtCurrentIndex
  );

  const hop = i + differenceBetweenEleAndEleAtIndex;

  if (i >= arr.length) {
    return;
  }
  if (arr[i] === ele) {
    return i;
  }

  const result = findMeAnElementsFunkyArray(arr, ele, hop);

  return result;
};

const array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

const answer = findMeAnElementsFunkyArray(array, 7, 0);

console.log(answer);

Wollte eine rekursive Lösung für das Problem enthalten. Genießen

Anthony Moon Beam Toorie
quelle