[JAVA] Gymnastique algorithmique 1

Binary Search on Arrays

La description

Un tableau qui stocke les entiers triés et la clé que vous recherchez est passé, et si cette clé est dans un tableau, il renvoie l'index de la clé. Si la clé n'existe pas, -1 est renvoyé.

Exemple

Tableau avec 47 touches et 20 éléments

Solution

Runtime Complexity: O(logn) Memory Complexity: O(logn)

La recherche binaire est utilisée pour trouver l'index d'un élément dans un tableau trié. Si l'élément n'existe pas, il peut être trouvé tout aussi efficacement. L'algorithme divise le tableau d'entrée en deux à chaque étape. Après chaque étape, vous pouvez supprimer la moitié du tableau pour voir si l'index que vous recherchez est trouvé. Par conséquent, la solution peut être calculée en temps O (logn).

Flux d'algorithme approximatif

1. Déterminez le plus bas du plus petit indice et le haut du plus grand indice, qui sont la plage à examiner par Array.
2. Trouvez la valeur du milieu au milieu du bas et du haut.
3. Si l'élément dans l'index de mid est le même que la clé, retournez mid.
4. S'il est plus grand que l'élément dans l'index de mid, high = mid -1. (Le bas reste tel quel)
5. S'il est plus petit que l'élément dans l'index de mid, low = mid + 1. (High reste le même)
6. Cependant, si low devient plus grand que high, la clé n'existe pas, donc -1 est renvoyé.

code

Supplément

La méthode itérative utilisant la boucle de roue au lieu de récursive a la même efficacité de vitesse, mais la complexité spatiale peut être O (1).