Moyen efficace de rechercher un élément

Récemment, j’ai eu une interview où ils m’ont posé une question “de recherche “.
La question était:

Supposons qu’il existe un tableau d’entiers (positifs), dont chaque élément est +1 ou -1 par rapport à ses éléments adjacents.

Exemple:

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

Maintenant, cherchez 7 et retournez sa position.

J’ai donné cette réponse:

Stockez les valeurs dans un tableau temporaire, sortingez-les, puis appliquez une recherche binary.

Si l’élément est trouvé, retournez sa position dans le tableau temporaire.
(Si le nombre se produit deux fois, retourne sa première occurrence)

Mais, ils ne semblaient pas être satisfaits de cette réponse.

Quelle est la bonne réponse?

Vous pouvez effectuer une recherche linéaire avec des étapes souvent supérieures à 1. L’observation cruciale est que si, par exemple, array[i] == 4 et 7 n’est pas encore apparu, le candidat suivant pour 7 est à l’indice i+3 . Utilisez une boucle while qui va directement au prochain candidat viable.

Voici une implémentation, légèrement généralisée. Il trouve la première occurrence de k dans le tableau (sous réserve de la ressortingction + = 1) ou -1 s’il ne se produit pas:

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

sortie:

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

Votre approche est trop compliquée. Vous n’avez pas besoin d’examiner chaque élément du tableau. La première valeur est 4 , donc 7 sont au moins 7-4 éléments, et vous pouvez les sauter.

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

Sortie du programme:

 Steps 4, index 11 

Edit: amélioré après les commentaires de @Raphael Miedl et @Martin Zabel.

Une variation de la recherche linéaire conventionnelle pourrait être une bonne solution. Choisissons un élément dit array[i] = 2 . Maintenant, le array[i + 1] sera soit 1 ou 3 (impair), le array[i + 2] sera (entiers positifs uniquement) 2 ou 4 (nombre pair).

En continuant ainsi, un motif est observable – le array[i + 2*n] contiendra des nombres pairs et tous ces indices peuvent être ignorés.

En outre, nous pouvons voir que

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

ainsi, l’index i + 5 doit être vérifié ensuite et une boucle while peut être utilisée pour déterminer le prochain index à vérifier, en fonction de la valeur trouvée à l’index i + 5 .

Bien que cela ait une complexité O(n) (temps linéaire en termes de complexité asymptotique), il vaut mieux en pratique qu’une recherche linéaire normale, car tous les indices ne sont pas visités.

Évidemment, tout cela sera inversé si le array[i] (notre sharepoint départ) était étrange.

L’approche présentée par John Coleman est ce que l’interviewer espérait, selon toute probabilité.
Si vous êtes prêt à aller un peu plus compliqué, vous pouvez augmenter la durée de saut attendue:
Appelez la valeur cible k . Commencez avec la valeur v du premier élément à la position p et appelez la différence kv dv avec la valeur absolue av . Pour accélérer les recherches négatives, examinez le dernier élément comme l’autre valeur u à la position o : si dv × du est négatif, k est présent (si une occurrence de k est acceptable, vous pouvez restreindre la plage d’index ici recherche binary fait). Si av + au est supérieur à la longueur du tableau, k est absent. (Si dv × du est zéro, v ou u est égal à k.)
Omettre la validité de l’index: Explorer la position (“next”) où la séquence pourrait retourner à v avec k au milieu: o = p + 2*av .
Si dv × du est négatif, trouvez k (récursivement?) De p + av à o-au;
si elle est nulle, u est égal à k en o.
Si du est égal à dv et que la valeur au milieu n’est pas k, ou au dépasse av,
ou vous ne trouvez pas k de p + av à o-au,
laisser p=o; dv=du; av=au; p=o; dv=du; av=au; et continuez à sonder.
(Pour un retour complet aux textes des années 60, voir avec Courier. Ma “1ère 2ème pensée” était d’utiliser o = p + 2*av - 1 , ce qui exclut du égal dv .)

ÉTAPE 1

Commencez avec le premier élément et vérifiez si c’est 7. Disons que c est l’index de la position actuelle. Donc, initialement, c = 0 .

ÉTAPE 2

Si c’est 7, vous avez trouvé l’index. C’est c . Si vous avez atteint la fin du tableau, éclatez.

ÉTAPE 3

Si ce n’est pas le cas, alors 7 doit être au moins |array[c]-7| positions loin car vous ne pouvez append qu’une unité par index. Par conséquent, Ajouter |array[c]-7| à votre index actuel, c, et passez à l’étape 2 à nouveau pour vérifier.

Dans le pire des cas, lorsqu’il existe des alternatives 1 et -1, la complexité temporelle peut atteindre O (n), mais la moyenne des cas sera fournie rapidement.

Ici, je donne l’implémentation en Java …

 public static void main(Ssortingng[] 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 

Voici une solution de style diviser-pour-conquérir. Au désortingment (beaucoup) de la comptabilité, nous pouvons sauter plus d’éléments; plutôt que de balayer de gauche à droite, testez au milieu et passez dans les deux directions.

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