Comment implémenter un algorithme de recherche binaire en Java sans récursivité

Une implémentation itérative de l'algorithme de recherche binaire populaire pour trouver un élément dans un tableau trié.

Bonjour à tous! J'ai publié de nombreux articles sur les algorithmes et les structures de données sur mon blog, mais celui-ci est le premier ici. Dans cet article, nous examinerons les algorithmes fondamentaux populaires pour les entretiens.

Oui, vous l'avez bien deviné: vous devez implémenter une recherche binaire en Java, et vous devez écrire des algorithmes de recherche binaire itérative et récursive.

En informatique, une recherche binaire, ou recherche demi-intervalle, est un algorithme de division et de conquête qui localise la position d'un élément dans un tableau trié. La recherche binaire fonctionne en comparant une valeur d'entrée à l'élément central du tableau.

La comparaison détermine si l'élément est égal à l'entrée, est inférieur à l'entrée ou est supérieur à l'entrée.

Lorsque l'élément comparé est égal à l'entrée, la recherche s'arrête et renvoie généralement la position de l'élément.

Si l'élément n'est pas égal à l'entrée, une comparaison est effectuée pour déterminer si l'entrée est inférieure ou supérieure à l'élément.

En fonction du résultat, l'algorithme recommence alors, mais ne recherche que le sous-ensemble supérieur ou inférieur des éléments du tableau.

Si l'entrée n'est pas située dans le tableau, l'algorithme produira généralement une valeur unique indiquant cela comme -1 ou lèvera simplement une RuntimeException en Java comme NoValueFoundException.

Les algorithmes de recherche binaire divisent généralement par deux le nombre d'éléments à vérifier à chaque itération successive, localisant ainsi l'élément donné (ou déterminant son absence) en temps logarithmique.

Btw, si vous n'êtes pas familier avec les algorithmes de recherche et de tri fondamentaux, vous pouvez également rejoindre un cours comme Structures de données et algorithmes: Deep Dive Using Java pour apprendre les algorithmes fondamentaux.

Si Java n'est pas votre choix de langage, vous pouvez trouver plus de recommandations pour JavaScript et Python dans cette liste de cours d'algorithmes.

Btw, si vous préférez les livres, je vous suggère de lire un livre complet sur les algorithmes comme Introduction aux algorithmes de Thomas H. Cormen.

Voici un exemple de code qui montre la logique de la recherche binaire itérative en Java :

Implémentation de la recherche binaire en Java

Voici un exemple de programme pour implémenter la recherche binaire en Java. L'algorithme est implémenté de manière récursive. De plus, un fait intéressant à connaître sur l'implémentation de la recherche binaire en Java est que Joshua Bloch, auteur du célèbre livre Effective Java, a écrit la recherche binaire dans «java.util.Arrays».

import java.util.Arrays;import java.util.Scanner;
/** * Java program to implement Binary Search. We have implemented Iterative* version of Binary Search Algorithm in Java** @author Javin Paul*/
public class IterativeBinarySearch {
 public static void main(String args[]) { int[] list = new int[]{23, 43, 31, 12}; int number = 12; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 12); System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
 binarySearch(list, 43); list = new int[]{123, 243, 331, 1298}; number = 331; Arrays.sort(list); System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
 binarySearch(list, 331); System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list)); binarySearch(list, 1333);
 // Using Core Java API and Collection framework // Precondition to the Arrays.binarySearch Arrays.sort(list);
 // Search an element int index = Arrays.binarySearch(list, 3);
}
/** * Perform a binary Search in Sorted Array in Java * @param input * @param number * @return location of element in array */
public static void binarySearch(int[] input, int number) {int first = 0;int last = input.length - 1;int middle = (first + last) / 2;
while (first <= last) { if (input[middle] < number) { first = middle + 1;} else if (input[middle] == number) {
System.out.printf(number + " found at location %d %n", middle);break;} else { last = middle - 1;}
middle = (first + last) / 2;
}
if (first > last) { System.out.println(number + " is not present in the list.\n");}
}
}
OutputBinary Search 12 in integer array [12, 23, 31, 43]12 found at location 0Binary Search 43 in integer array [12, 23, 31, 43]43 found at location 3Binary Search 331 in integer array [123, 243, 331, 1298]331 found at location 2Binary Search 331 in integer array [123, 243, 331, 1298]1333 is not present in the list.

C'est tout sur la façon d'implémenter la recherche binaire à l'aide de la récursivité en Java . Avec la recherche linéaire, ce sont deux des algorithmes de recherche essentiels que vous apprenez dans votre cours d'informatique.

La structure de données de l'arborescence de recherche binaire tire parti de cet algorithme et organise les données dans une structure hiérarchique afin que vous puissiez rechercher n'importe quel nœud dans le temps O (logN).

Cependant, vous devez vous rappeler que pour utiliser la recherche binaire, vous avez besoin d'une liste ou d'un tableau triés, vous devez donc également prendre en compte le coût du tri lorsque vous envisagez d'utiliser un algorithme de recherche binaire dans le monde réel.

Apprentissage supplémentaire

Structures de données et algorithmes: analyse approfondie de Java

Algorithmes et structures de données - Parties 1 et 2

Structures de données en Java 9 par Heinz Kabutz

10 livres d'algorithmes pour les interviews

10 cours sur la structure des données et l'algorithme pour les entretiens

5 cours gratuits pour apprendre la structure des données et les algorithmes

Autres didacticiels sur la structure des données et les algorithmes susceptibles de vous plaire

  • Comment implémenter l'algorithme Quicksort en place en Java? (Didacticiel)
  • Comment implémenter l'arbre de recherche binaire en Java? (Solution)
  • Comment implémenter l'algorithme Quicksort sans récursivité? (Didacticiel)
  • Comment implémenter l'algorithme de tri par insertion en Java? (Didacticiel)
  • Comment implémenter l'algorithme de tri à bulles en Java? (Didacticiel)
  • Quelle est la différence entre l'algorithme de tri basé sur la comparaison et la non-comparaison? (répondre)
  • Comment implémenter Bucket Sort en Java? (Didacticiel)
  • Comment implémenter un algorithme de recherche binaire sans récursivité en Java? (Didacticiel)
  • Plus de 50 cours sur la structure des données et les algorithmes pour les programmeurs (questions)

Merci d'avoir lu cet article. Si vous aimez cet article, partagez-le avec vos amis et collègues. Si vous avez des suggestions ou des commentaires, veuillez laisser un commentaire.

PS - Si vous voulez vraiment améliorer vos compétences en algorithmes, je pense que les structures de données et les algorithmes: Deep Dive Using Java est le meilleur pour commencer.