Un moyen efficace de rechercher un élément

Question

Récemment, j'ai eu un entretien au cours duquel on m'a posé une " recherche Question ".
La question était :

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

Ejemplo:

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

Maintenant, cherchez 7 et retourner sa position.

J'ai donné cette réponse :

Stockez les valeurs dans un tableau temporaire, triez-les, puis appliquez la recherche binaire.

Si l'élément est trouvé, on retourne sa position dans le tableau temporaire.
(Si le nombre apparaît deux fois, il faut retourner sa première occurrence).

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

Quelle est la bonne réponse ?

Answer 1

Vous pouvez effectuer une recherche linéaire avec des étapes qui sont souvent supérieures à 1. L'observation cruciale est que si par exemple array[i] == 4 et que 7 n'est pas encore apparu alors le prochain candidat pour 7 est à l'indice i+3 . Utilisez une boucle while qui passe directement au candidat viable suivant de manière répétée.

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

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

sortie :

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

Answer 2

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 est au moins 7-4 et vous pouvez les ignorer.

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

Sortie du programme :

Steps 4, index 11

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

Answer 3

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

En continuant comme ça, un modèle est observable - array[i + 2*n] contiendra des nombres pairs et donc tous ces indices peuvent être ignorés.

Aussi, nous pouvons voir que

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

donc, indice i + 5 doit être vérifié ensuite et une boucle while peut être utilisée pour déterminer l'indice suivant à vérifier, en fonction de la valeur trouvée à l'indice i + 5 .

Bien que, cela a la complexité O(n) (temps linéaire en termes de complexité asymptotique), elle est meilleure qu'une recherche linéaire normale en termes pratiques car tous les indices ne sont pas visités.

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

Answer 4

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 loin, vous pouvez augmenter la longueur prévue du saut :
Appeler la valeur cible k . Commencez par la valeur du premier élément v à la position p et on appelle la différence k-v dv avec une valeur absolue av . Pour accélérer les recherches négatives, jetez un coup d'œil au dernier élément comme l'autre valeur. u à la position o si dv×du est négatif, k est présent (si toute occurrence de k est acceptable, vous pouvez réduire la plage d'index ici à la manière de la recherche binaire). Si av+au est supérieur à la longueur du tableau, k est absent. (Si dv×du est nul, v ou u est égal à k).
Omettre la validité de l'indice : Sondez la position ("suivante") où la séquence pourrait revenir à v avec k au milieu : o = p + 2*av .
Si dv×du est négatif, trouver k (par récurrence ?) de p+av à o-au ;
si elle est nulle, u est égale à k en o.
Si du est égal à dv et que la valeur au milieu n'est pas k, ou si au dépasse av,
ou vous échouer pour trouver le k de p+av à o-au,
let p=o; dv=du; av=au; et continuez à sonder.
(Pour un flash-back complet sur les textes des années 60, voir avec Courier. Ma "1ère 2ème idée" était d'utiliser o = p + 2*av - 1 ce qui exclut du est égal à dv .)

Answer 5

ÉTAPE 1

Commencez par le premier élément et vérifiez si c'est 7. Disons que c est l'indice 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, sortez.

ÉTAPE 3

S'il ne l'est pas, alors 7 doit être au moins |array[c]-7| parce que vous ne pouvez ajouter qu'une unité par indice. Par conséquent, Ajouter |array[c]-7| à votre indice actuel, c, et passez de nouveau à l'ÉTAPE 2 pour vérifier.

Dans le pire des cas, lorsqu'il y a alternativement des 1 et des -1, la complexité temporelle peut atteindre O(n), mais les cas moyens seraient livrés rapidement.