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 l'un +1ou l' autre ou -1comparé à ses éléments adjacents.

Exemple:

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

Recherchez maintenant 7et restaurez 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é, retournez sa position dans le tableau temporaire.
(Si le nombre se produit deux fois, renvoie sa première occurrence)

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

Quelle est la bonne réponse?

Vous pouvez faire une recherche linéaire avec des pas qui sont souvent supérieurs à 1. L'observation cruciale est que si par exemple array[i] == 4et 7 n'est pas encore apparu, le prochain candidat pour 7 est à l'index i+3. Utilisez une boucle while qui va à plusieurs reprises directement au prochain candidat viable.

Voici une implémentation, légèrement généralisée. Il trouve la première occurrence de kdans le tableau (sous réserve de la restriction + = 1) ou -1si elle 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;
}

production:

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, il en 7va de même pour au moins les 7-4 éléments, 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.

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

En continuant ainsi, un modèle est observable - array[i + 2*n]contiendra des nombres pairs et ainsi 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

Ainsi, l'index i + 5doit ê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 soit complexe O(n)(temps linéaire en termes de complexité asymptotique), il vaut mieux 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.

L'approche présentée par John Coleman est ce que l'intervieweur espérait, selon toute probabilité.
Si vous êtes prêt à aller un peu plus compliqué, vous pouvez augmenter la longueur de saut attendue:
Appelez la valeur cible k . Commencez par la valeur du premier élément v à la position p et appelez la différence kv dv avec la valeur absolue av . Pour accélérer les recherches négatives, jetez un œil au 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 comme le fait la recherche binaire). Si av + au est supérieur à la longueur du tableau, k est absent. (Si dv × du zéro est, v ou u est égal à k.)
Omettre validité d'index: sonde le ( « suivant ») position où la séquence pourrait revenir à v avec k au milieu: o = p + 2*av.
Si dv × du est négatif, trouver k (récursivement?) De p + av à o-au;
s'il est nul, u vaut k en o.
Si du est égal à dv et que la valeur au milieu n'est pas k, ou au dépasse av,
ou si vous ne trouvez pas k de p + av à o-au,
laissez p=o; dv=du; av=au;et continuez à sonder.
(Pour un flash-back complet sur les textes des années 60, regardez avec Courier. Ma "1ère 2ème pensée" était d'utilisero = p + 2*av - 1, ce qui exclut du égal à dv .)

ÉTAPE 1

Commencez par le premier élément et vérifiez s'il est 7. Disons que cc'est l'indice de la position actuelle. Donc, au départ, 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

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

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

Ici, je donne l'implémentation en 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;
}

Voici une solution de style diviser et conquérir. Au détriment de (beaucoup) plus de comptabilité, nous pouvons sauter plus d'éléments; plutôt que de balayer de gauche à droite, testez au milieu et sautez dans les deux sens.

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

}

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

Voulait inclure une solution récursive au problème. Prendre plaisir