Question d'entretien - Rechercher dans un tableau trié X l'indice i tel que X[i] = i

Question

On m'a posé la question suivante lors de mon entretien d'hier :

Considérons un tableau Java ou C++, par exemple X qui est trié et dont deux éléments ne sont pas identiques. Comment trouver au mieux un index dire i tel que l'élément à cet indice est aussi i . C'est-à-dire X[i] = i .

En guise de clarification, elle m'a également donné un exemple :

Array X : -3 -1 0 3 5 7
index   :  0  1 2 3 4 5

Answer is 3 as X[3] = 3.

Le mieux que j'ai pu imaginer était une recherche linéaire. Après l'entretien, j'ai beaucoup réfléchi à ce problème mais je n'ai pas trouvé de meilleure solution. Mon argument est le suivant : l'élément avec la propriété requise peut se trouver n'importe où dans le tableau. Il peut donc aussi se trouver à la fin du tableau et nous devons vérifier chaque élément.

Je voulais juste que la communauté me confirme que j'ai raison. S'il vous plaît, dites-moi que j'ai raison :)

Answer 1

Cela peut être fait dans O(logN) temps et O(1) en utilisant une méthode légèrement modifiée recherche binaire .

Considérons un nouveau tableau Y tal que Y[i] = X[i] - i

Array X : -3 -1   0  3  5  7
index   :  0  1   2  3  4  5
Array Y : -3 -2  -2  0  1  2

Puisque les éléments dans X sont en augmentation de dans l'ordre, les éléments de la nouveau tableau Y sera dans non décroissant ordre. Ainsi, un binaire recherche para 0 en Y donnera la réponse.

Mais créer Y prendra O(N) l'espace et O(N) temps. Ainsi, au lieu de créer un nouveau tableau, il suffit de modifier la recherche binaire de telle sorte qu'une référence à Y[i] est remplacé par X[i] - i .

Algorithme :

function (array X) 
       low  = 0
       high = (num of elements in X) - 1

       while(low <= high) 
               mid = (low + high) / 2

               // change X[mid] to X[mid] - mid
               if(X[mid] - mid == 0)
                       return mid

               // change here too
               else if(X[mid] - mid < 0)
                       low = mid + 1;

               else
                       high = mid - 1;
       end while

       return -1 // no such index exists...return an invalid index.

end function

Mise en œuvre de Java

Mise en œuvre du C++

Answer 2

Il existe des solutions plus rapides, en moyenne O(log n) ou dans certains cas O(log log n) au lieu de O(n). Cherchez sur Google "recherche binaire" y "recherche par interpolation" vous avez toutes les chances de trouver de très bonnes explications.

Si le tableau n'est pas trié, alors oui, l'élément est n'importe où et vous ne pouvez pas descendre en dessous de O(n), mais ce n'est pas le cas avec les tableaux triés.

--

Quelques explications sur la recherche par interpolation, comme demandé :

Alors que la recherche binaire ne s'intéresse qu'à la comparaison de deux éléments en termes de "plus grand / moins grand", la recherche par interpolation tente d'utiliser également les critères suivants valeurs numériques . Le problème est le suivant : Vous avez une plage triée de valeurs allant de 0 à, disons, 20000. Vous cherchez 300 - la recherche binaire commence à la moitié de la plage, à 10000. La recherche par interpolation suppose que 300 serait probablement plus proche de 0 que de 20000, et qu'elle vérifierait donc d'abord l'élément 6000 au lieu de 10000. Mais encore une fois, si la valeur est trop élevée, la recherche se fait dans la sous-gamme inférieure, et si elle est trop faible, la recherche se fait dans la sous-gamme supérieure.

Pour un grand tableau avec +- une distribution uniforme des valeurs, la recherche par interpolation devrait se comporter beaucoup plus rapidement que la recherche binaire - codez-le et voyez par vous-même. De même, le fonctionnement est optimal si vous utilisez d'abord une étape de recherche par interpolation, puis une étape de recherche binaire, et ainsi de suite.

Notez que c'est la chose qu'un humain fait intuitivement lorsqu'il cherche quelque chose dans un dictionnaire.

Answer 3

Il n'est pas nécessaire de penser en termes de tableau. Y comme suggéré dans réponse par @codaddict.

Utilisez la recherche binaire et vérifiez l'élément central d'un tableau donné, s'il est inférieur à son index, alors nous n'avons pas besoin de vérifier pour un index inférieur parce que le tableau est trié et donc si nous nous déplaçons vers la gauche, en soustrayant m indices et (au moins) m valeurs, tous les éléments suivants seront également trop petits. Par exemple, si arr[5] = 4 entonces arr[4] <= (4 - 1) y arr[3] <= (4 - 2) et ainsi de suite. Une logique similaire peut être appliquée si l'élément central est plus grand que son index.

Voilà qui est simple Java mise en œuvre :

int function(int[] arr) {
        int low = 0;
        int high = arr.length - 1;

        while(low <= high) {
            int mid = high - (high - low) / 2;

            if(arr[mid] == mid) {
                 return mid;
            } else if(arr[mid] < mid) {
                 low = mid + 1;
            } else {
                 high = mid - 1;
            }
        }

        return -1; // There is no such index
}

Notez que la solution ci-dessus ne fonctionne que si tous les éléments sont distincts.

Answer 4

Je pense que ce serait plus rapide.

Commencez au milieu de la liste

Si X[i] > i alors aller au milieu du côté gauche restant

si X[i] < i alors aller au milieu de la droite restante

Continuez à faire cela et vous réduirez de moitié le nombre d'éléments possibles pour chaque boucle.

Answer 5

Vous pouvez effectuer une recherche binaire : chercher au milieu, si la valeur est inférieure à l'index, alors aucun index inférieur ne contiendra la même valeur.

Ensuite, vous recherchez la moitié supérieure, et continuez jusqu'à ce que vous trouviez l'élément, ou que vous atteigniez la portée d'un élément.