Algorithme de recherche binaire en Java

1. Vue d'ensemble

Dans cet article, nous aborderons les avantages d'une recherche binaire par rapport à une simple recherche linéaire et découvrirons son implémentation en Java.

2. Besoin d'une recherche efficace

Disons que nous sommes dans le secteur de la vente de vin et que des millions d'acheteurs visitent notre application chaque jour.

Grâce à notre application, un client peut filtrer les articles dont le prix est inférieur à n dollars, sélectionner une bouteille dans les résultats de recherche et les ajouter à son panier. Nous avons des millions d'utilisateurs à la recherche de vins avec une limite de prix par seconde. Les résultats doivent être rapides.

Sur le backend, notre algorithme exécute une recherche linéaire dans toute la liste des vins en comparant la limite de prix saisie par le client avec le prix de chaque bouteille de vin de la liste.

Ensuite, il renvoie les articles dont le prix est inférieur ou égal à la limite de prix. Cette recherche linéaire a une complexité temporelle de O (n) .

Cela signifie que plus le nombre de bouteilles de vin dans notre système est élevé, plus cela prendra de temps. Le temps de recherche augmente proportionnellement au nombre de nouveaux éléments introduits.

Si nous commençons à enregistrer les éléments dans un ordre trié et à rechercher des éléments à l'aide de la recherche binaire, nous pouvons atteindre une complexité de O (log n) .

Avec la recherche binaire, le temps pris par les résultats de la recherche augmente naturellement avec la taille de l'ensemble de données, mais pas proportionnellement.

3. Recherche binaire

En termes simples, l'algorithme compare la valeur de clé avec l'élément du milieu du tableau; s'ils sont inégaux, la moitié dans laquelle la clé ne peut pas faire partie est éliminée et la recherche continue pour la moitié restante jusqu'à ce qu'elle réussisse.

Rappelez-vous - l'aspect clé ici est que le tableau est déjà trié.

Si la recherche se termine avec la moitié restante vide, la clé n'est pas dans le tableau.

3.1. Impl itératif

public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid]  key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }

La méthode runBinarySearchIterately prend un sortedArray , une clé et les index bas et haut de sortedArray comme arguments. Lorsque la méthode s'exécute pour la première fois, le bas , le premier index de sortedArray, est 0, tandis que le haut , le dernier index du sortedArray, est égal à sa longueur - 1.

Le milieu est l'index du milieu de sortedArray . Maintenant , l'algorithme exécute une en boucle comparant la clé avec la valeur du tableau de l'indice du milieu sortedArray .

3.2. Impl récursif

Voyons maintenant une implémentation simple et récursive:

public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } 

La méthode runBinarySearchRecursively accepte un sortedArray , une clé, les index bas et haut de sortedArray .

3.3. Utilisation de tableaux. recherche binaire()

int index = Arrays.binarySearch(sortedArray, key); 

Un sortedArray et une clé int , qui doivent être recherchés dans le tableau d'entiers, sont transmis en tant qu'arguments à la méthode binarySearch de la classe Java Arrays .

3.4. Utilisation des collections. recherche binaire()

int index = Collections.binarySearch(sortedList, key); 

Une sortedList et une clé Integer , qui doit être recherchée dans la liste des objets Integer , sont transmises comme arguments à la méthode binarySearch de la classe Java Collections .

3.5. Performance

Le fait d'utiliser une approche récursive ou itérative pour écrire l'algorithme est principalement une question de préférence personnelle. Mais voici encore quelques points dont nous devons être conscients:

1. La récursivité peut être plus lente en raison de la surcharge de maintenance d'une pile et prend généralement plus de mémoire

2. La récursivité est pas stack- amical. Cela peut provoquer une exception StackOverflowException lors du traitement de grands ensembles de données

3. La récursivité ajoute de la clarté au code car elle le raccourcit par rapport à l'approche itérative

Idéalement, une recherche binaire effectuera moins de comparaisons par rapport à une recherche linéaire de grandes valeurs de n. Pour des valeurs plus petites de n, la recherche linéaire pourrait être plus performante qu'une recherche binaire.

Il faut savoir que cette analyse est théorique et peut varier selon le contexte.

En outre, l'algorithme de recherche binaire a besoin d'un ensemble de données triées qui a également ses coûts . Si nous utilisons un algorithme de tri par fusion pour trier les données, une complexité supplémentaire de n log n est ajoutée à notre code.

Nous devons donc d'abord bien analyser nos exigences, puis prendre une décision sur l'algorithme de recherche qui correspond le mieux à nos exigences.

4. Conclusion

Ce didacticiel a présenté une implémentation d'algorithme de recherche binaire et un scénario dans lequel il serait préférable de l'utiliser au lieu d'une recherche linéaire.

Veuillez trouver le code du didacticiel sur GitHub.