algorithme pour trouver s'il y a un i si ce tableau [i] i est égal à

Question

J'ai une mission de mon professeur CS:

Trouvez, en O (log n) temps, si dans un prétriés étant donné tableau d'entiers distincts il y a un index i de sorte que array [i] = i. Montrer que l'heure est O (logn).

Mise à jour: Les nombres entiers peuvent être négatifs, 0 ou positifs.

Très bien, j'ai donc eu un peu de mal avec ça. Mon idée est la suivante:

En utilisant la recherche binaire, nous pouvons seulement être certain qu'il n'y a pas une telle valeur à gauche de l'élément central si array [mid] < = startindex, où mid est l'indice de l'élément central, et startindex est le début du tableau.

La règle correspondante pour la moitié droite d'un tableau est ce tableau [mid]> = startindex + numel, où les variables comme ci-dessus et numel est le nombre d'éléments à droite de mid.

Cela ne semble pas O (logn), puisque dans le pire des cas, je dois itérer à travers le tout, non? Est-ce que quelqu'un peut me donner un pourboire dans la bonne direction ou me dire que ça fonctionne?

Des idées comment je pourrais prouver formellement cela? Je ne demande pas de réponse définitive, plus d'aide pour me faire comprendre.

En C:

int _solve_prob_int(int depth, int start, int count, int input[]) 
    { 
    if(count == 0) 
     return 0; 
    int mid = start + ((count - 1)/2); 
    if(input[mid] == mid) 
     return 1; 

    if(input[mid] <= start && input[mid] >= start + count) 
     return 0; 

    int n_sub_elleft = (int)(count - 1)/2; 
    int n_sub_elright = (int)(count)/2; 

    if(input[mid] <= start) 
     return _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input); 

    if(input[mid] >= start + count) 
     return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input); 

    return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input) || 
      _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input); 
    } 

Un cas de test:

Sorted args: 1 2 3 4 5 6 7 8 9 10 11 12 : 
Start: 0, count: 12, mid: 5 value: 6 
    Start: 0, count: 5, mid: 2 value: 3 
     Start: 0, count: 2, mid: 0 value: 1 
      Start: 1, count: 1, mid: 1 value: 2 
     Start: 3, count: 2, mid: 3 value: 4 
      Start: 4, count: 1, mid: 4 value: 5 
    Start: 6, count: 6, mid: 8 value: 9 
     Start: 6, count: 2, mid: 6 value: 7 
      Start: 7, count: 1, mid: 7 value: 8 
     Start: 9, count: 3, mid: 10 value: 11 
      Start: 9, count: 1, mid: 9 value: 10 
      Start: 11, count: 1, mid: 11 value: 12 

Ce qui précède est ma fonctionner avec une sortie en fonction de la façon dont il recherche programme. Avec une liste de 1 à 12, il pivote autour de l'index 5, détermine qu'il pourrait y avoir une valeur entre 0-4 aux index 0-4. Il détermine également qu'il pourrait y avoir une valeur entre 6-11 aux index 6-11. Ainsi, je procède à une recherche les deux. Est-ce mal?

Answer 1

Les nombres entiers sont distincts et triés.

Étant donné que j'ai array[i] = i vous avez array[i] - i = 0.

Pour chaque j < i vous avez array[j] - j <= 0 et j> i vous avez array[j] - j >= 0 parce que j varie de 1 à chaque étape, mais array [j] varier d'au moins 1 (distincts et triés numéros).

Donc à gauche c'est <=0 sur la droite c'est >= 0.

En utilisant la dichotomie, vous pouvez facilement trouver la position correcte dans O(log n).

---

S'il vous plaît noter que vous avez seulement besoin de trouver un élément, pas tous. Dans votre exemple, tous les éléments fonctionnent mais vous n'en avez besoin que d'un seul. Si vous voulez les imprimer tous, ce sera O(n) ..

Answer 2

Votre intuition est juste d'utiliser la recherche binaire; votre analyse ne l'est pas. Rappelez-vous qu'il s'agit d'une liste triée, donc dans la condition de recherche binaire, vous devez rechercher un MAXIMUM d'entrées de journal (n).

Answer 3

Pensez à une recherche binaire comme chercher un mot dans le dictionnaire.Vous pouvez commencer en ouvrant le livre exactement au centre du dictionnaire, et voir si le mot en haut de la page est avant, après ou égal au mot que vous recherchez. Si c'est après, vous divisez la deuxième moitié du dictionnaire en deux et vérifiez le milieu de cette moitié. Après avoir regardé en haut de la page, vous avez réduit la zone que vous cherchez à environ un quart du dictionnaire. Vous continuez ce processus jusqu'à ce que vous trouviez que le mot est quelque part sur la page que vous regardez. Ensuite, vous utilisez un processus similaire pour trouver le mot sur cette page.

Ce processus n'est pas O (n) parce que vous n'avez pas eu à regarder chaque mot sur chaque page, même dans le pire des cas. C'est O (log n), car à chaque étape, vous étiez en mesure d'éliminer environ la moitié du dictionnaire pas contenant le mot que vous cherchiez.

Modifier

Désolé, j'ai mal compris le problème d'origine. Dans ce cas, la clé est de reconnaître ce que l'on appelle le «principe du trou de pigeon», qui stipule que vous ne pouvez placer autant de pigeons dans les trous que si vous avez des trous pour les ajuster. le milieu universitaire à venir avec un nom pour une idée si simple)

Prenons le cas suivant:

0 1 2 3 4 5 6 

ici, tousarray[i] sont égaux à i, donc quand vous commencez votre recherche binaire, vous aurez immédiatement une réponse positive.

Maintenant, nous allons prendre un nombre au bas:

0 1 3 4 5 6 

Lorsque vous faites votre recherche binaire, vous verrez que array[3] > 3, et vous pouvez correctement en déduire qu'aucune valeur supérieure à ce point de pivot pourrait faire . En effet, la liste est ordonnée et unique, de sorte que vous ne pouvez pas finir avec des combinaisons comme celles-ci:

0 1 3 4 5 5 6 
0 1 3 4 6 5 7 

Une fois array[i] est déterminé à être supérieure à i, il y a tout simplement pas assez de nombres entre i et tout n pour permettre à l'élément suivant du tableau de se rapprocher de i. De même, si vous déterminez que array[i] est inférieur à i, vous n'avez pas assez de "trous" disponibles pour "rattraper" i lorsque vous regardez vers le début du tableau. Par conséquent, à chaque étape, vous pouvez éliminer correctement la moitié du tableau et, tout comme dans un dictionnaire, déterminer si en 0 (journal n).

Answer 4

Je vais essayer de ne pas donner la réponse, mais je vais signaler quelques observations:

Lors de l'examen de l'élément du milieu, il y a 3 cas. Le premier est bien sûr ce tableau [i] == i, auquel cas l'algorithme se termine. Dans les deux autres cas, nous sommes capables de rejeter l'élément lui-même ainsi que la moitié de l'entrée.

Maintenant, si array [i]> i, est-il possible que l'index de tableau (i) "rattrape" les valeurs du tableau lorsque nous nous déplaçons vers la droite? Gardez à l'esprit les propriétés distinctes triées des valeurs du tableau.

Answer 5

Ceci est un problème de recherche binaire avec la clé non donnée. Dans la question d'OP, la clé est le milieu même! Voilà, recherchez mid element dans chaque sous-tableau.

pseudocode de la solution en utilisant la recherche binaire:

while (low and high don't meet) 
     mid = (low + high)/2 
     if (arr[mid] < mid) 
      high = mid - 1 
     else if (arr[mid] > mid) 
      low = mid + 1 
     else // we found it! 
      return mid; 
    // end while 
    return -1; // indicates there is no such i 

Answer 6

depuis tableau A est triée. A [i]> = A [i-1] +1 => A [i] -i> = A [i-1] - (i-1), soit B [i] = A [i] -i, B [] est un tableau trié qui peut être recherché par B [x] == 0 en temps lgn en utilisant la recherche binaire.

Answer 7

Array B[i] = A[i]-i ne peut pas être triés même si A [i] est trié, mais a des doublons:

Considérons cet exemple:

i: 0 1 2 3 4
A: 1 1 2 4 4

B [0] = a [0] = 1 -0, B [1] = A [1] -1 = 0, ...

B: 1 0 0 1 0

Answer 8

public static int fixedPoint(int[] array, int start, int end) { 

    if (end < start || start < 0 || end >= array.length) { 
     return -1; 
    } 
    int midIndex = start +(end-start)/ 2; 
    int midValue = array[midIndex]; 
    if (midValue == midIndex) {//trivial case 
     return midIndex; 
    } 
    // if there are duplicates then we can't conclude which side (left or right) will 
    // have the magic index. so we need to search on both sides 
    //but, we can definitely exclude few searches. 
    // take the example of the array : 
    // 0 1 2 3 4 5      6 7 8 9 10 -> indices 
    // -10, -5, 2, 2, 2, 3(midVal, midIndex = 5), 4, 7, 9, 12, 13 -> array element 
    // here, midValue < midIndex, but we can't say for sure which side to exclude 
    // as you can see there are two such magic indices. A[2] = 2 and A[7] = 7. so 
    // we need to search both sides 
    // since midValue < midIndex, then we can be sure that between index can't be 
    // between index number midValue and midIndex-1 

    /* Search left */ 
    int leftIndex = Math.min(midIndex - 1, midValue); 
    int left = fixedPoint(array, start, leftIndex); 
    if (left >= 0) { 
     return left; 
    } 

    /* Search right */ 
    int rightIndex = Math.max(midIndex + 1, midValue); 
    int right = fixedPoint(array, rightIndex, end); 

    return right; 
} 

public static int fixedPoint(int[] array) { 
    return fixedPoint(array, 0, array.length - 1); 
}