BINARY RECHERCHE ALGORITHME (Java, C), les algorithmes et structures de données
Besoin d'aide avec une mission de programmation? Obtenez de l'aide aux devoirs de programmation abordable.
En général, pour trouver une valeur dans le tableau non trié, nous devons regarder à travers des éléments d'un tableau, un par un, jusqu'à ce que la valeur recherchée se trouve. En cas de valeur recherchée est absente du tableau, nous passons par tous les éléments. En moyenne, la complexité d'un tel algorithme est proportionnelle à la longueur du tableau.
La situation change de manière significative, lorsque tableau est trié. Si nous le savons, la capacité d'accès aléatoire peut être utilisé de façon très efficace pour trouver la valeur recherchée rapidement. Le coût de l'algorithme de recherche réduit à logarithme binaire de la longueur du tableau. Pour référence, log2 (1 000 000) ≈ 20. Cela signifie que, dans le pire des cas. algorithme fait 20 étapes pour trouver une valeur dans le tableau d'un million Sorted éléments ou à dire, qu'il ne présente pas le tableau.
L'algorithme est assez simple. Il peut se faire soit de façon récursive ou itérativement:
- obtenir l'élément central;
- si l'élément intermédiaire est égal à la valeur recherchée, l'algorithme arrête;
- sinon, deux cas sont possibles:
- La valeur recherchée est inférieure, de l'élément intermédiaire. Dans ce cas, passez à l'étape 1 pour la partie du tableau, avant élément central.
- La valeur recherchée est plus grande, que l'élément intermédiaire. Dans ce cas, passer à l'étape 1 pour la partie de la matrice, après l'élément intermédiaire.
Maintenant, nous devons définir, quand les itérations doivent cesser. Le premier cas est lorsque l'élément recherché se trouve. La deuxième est quand n'a pas d'éléments sous-tableau. Dans ce cas, nous pouvons conclure que la valeur recherchée ne présente pas dans le tableau.
Etape 1 (l'élément du milieu est 19> 6): 5 6 18 -1 19 25 46 78 102 114
Etape 2 (élément du milieu est 5 < 6): -1 5 6 18 19 25 46 78 102 114
Etape 3 (l'élément du milieu est 6 == 6): 5 6 18 -1 19 25 46 78 102 114
Etape 1 (l'élément du milieu est 19 < 103): -1 5 6 18 19 25 46 78 102 114
Etape 2 (élément médian est de 78 < 103): -1 5 6 18 19 25 46 78 102 114
Etape 3 (l'élément du milieu est 102 < 103): -1 5 6 18 19 25 46 78 102 114
Etape 4 (élément médian est de 114> 103): 5 6 18 -1 19 25 46 78 102 114
Etape 5 (valeur recherchée est absente): 5 6 18 -1 19 25 46 78 102 114
Analyse de la complexité
énorme avantage de cet algorithme est que sa complexité dépend de la taille du tableau dans logarithmiquement pire des cas. En pratique, cela signifie que l'algorithme fera au plus itérations log2 (n), ce qui est un très petit nombre, même pour les grands tableaux. Il peut être prouvé très facilement. En effet, à chaque pas la taille de la pièce recherchée est réduite de moitié. arrête l'algorithme, quand il n'y a pas d'éléments à rechercher dans Par conséquent, la résolution suivante inégalités en nombres entiers.:
n / 2 itérations> 0
itérations <= log2 (n).
Cela signifie que la complexité temporelle de l'algorithme de recherche binaire est O (log2 (n)).
Extraits de code.
Vous pouvez voir la solution récursive pour Java et itérative pour C ++ ci-dessous.
* recherches pour une valeur dans le tableau trié