Effiziente Möglichkeit, ein Element zu suchen

Kürzlich hatte ich ein Vorstellungsgespräch, wo sie mich fragten: „suchen” Frage.
Die Frage war:

Angenommen, es gibt ein Array von (positiven) ganzen Zahlen, von denen jedes Element eines von beiden ist +1 oder -1 im Vergleich zu den angrenzenden Elementen.

Beispiel:

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

Jetzt suchen 7 und seine Position zurückgeben.

Ich habe diese Antwort gegeben:

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?

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

Hier ist eine leicht verallgemeinerte Implementierung. Es findet das erste Vorkommen von k im Array (vorbehaltlich der Einschränkung +=1) oder -1 wenn es nicht vorkommt:

#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;
}

Ausgang:

7 first occurs at index 11
but 9 first "occurs" at index -1

Dein Ansatz ist zu kompliziert. Sie müssen nicht jedes Array-Element untersuchen. Der erste Wert ist 4Also 7 ist wenigstens 7-4 Elemente weg, 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: nach Kommentaren von @Martin Zabel verbessert.

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, array[i + 1] ist entweder 1 oder 3 (ungerade), array[i + 2] wird (nur positive ganze Zahlen) 2 oder 4 (gerade Zahl).

Wenn man so weitermacht, ist ein Muster zu beobachten – array[i + 2*n] enthält gerade Zahlen und daher können alle diese Indizes ignoriert werden.

Auch das können wir sehen

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

also Index i + 5 sollte als nächstes geprüft werden und eine While-Schleife kann verwendet werden, um den nächsten zu prüfenden Index zu bestimmen, abhängig von dem Wert, der bei Index gefunden wird i + 5.

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

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

Der von John Coleman vorgestellte Ansatz entspricht aller Wahrscheinlichkeit nach dem, was sich der Interviewer erhofft hatte.
Wenn Sie bereit sind, etwas komplizierter vorzugehen, können Sie die erwartete Sprunglänge erhöhen:
Rufen Sie den Zielwert auf k. Beginnen Sie mit dem Wert des ersten Elements v an Stelle p und nenne die Differenz kv dv mit absolutem Wert ein V. Um negative Suchen zu beschleunigen, werfen Sie einen Blick auf das letzte Element als anderen Wert u an Stelle Ö: Wenn dv×du negativ ist, ist k vorhanden (wenn irgendein Vorkommen von k akzeptabel ist, können Sie den Indexbereich hier eingrenzen, wie es die binäre Suche tut). 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 zu v mit k in der Mitte 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 du gleich dv ist und der Wert in der Mitte nicht k ist oder au größer als av ist,
oder du scheitern um k von p+av bis o-au zu finden,
Lassen p=o; dv=du; av=au; und probier weiter.
(Für einen vollständigen Rückblick auf die Texte der 60er Jahre, siehe Courier. Mein “erster zweiter Gedanke” war zu verwenden o = p + 2*av - 1was ausschließt du ist gleich dv.)

SCHRITT 1

Beginnen Sie mit dem ersten Element und prüfen Sie, ob es 7 ist. Sagen wir c ist der 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 nicht, dann muss mindestens 7 sein |array[c]-7| Positionen entfernt, weil Sie nur eine Einheit pro Index hinzufügen können. Daher hinzufügen |array[c]-7| zu Ihrem aktuellen Index, c, 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.

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;
}

Hier ist eine Lösung im Teile-und-Herrsche-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 springen Sie hinein 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;                                                                     

}