Qu'est-ce que la recherche binaire en Java? Comment le mettre en œuvre?

Les algorithmes de recherche et de tri sont les algorithmes populaires dans tous les langages de programmation. Ils sont la base pour comprendre les principes fondamentaux de la programmation. Un de ces algorithmes de recherche populaires est la recherche binaire dans . Dans cet article, je vais vous dire tout sur sa mise en œuvre.

Les sujets ci-dessous sont traités dans cet article:

• Qu'est-ce que la recherche binaire?
• Implémentation de l'algorithme de recherche binaire
• Recherche binaire récursive

Commençons!

Qu'est-ce que la recherche binaire?

Recherche binaire dans est un algorithme de recherche qui trouve la position d'une valeur cible dans un tri tableau . Recherche binaire compare la valeur cible à l'élément central du tableau. Ilfonctionne uniquement sur un ensemble d'éléments triés. Pour utiliser la recherche binaire sur une collection, le doit d'abord être trié.

Quand le est utilisé pour effectuer des opérations sur un ensemble trié, le nombre d'itérations peut toujours être réduit en fonction de la valeur recherchée. Vous pouvez voir dans l'instantané ci-dessus pour trouver le élément central . L'analogie de la recherche binaire consiste à utiliser les informations que le tableau est trié et à réduire la complexité temporelle à O (log n) .

Implémentation de l'algorithme de recherche binaire

Jetons un coup d'œil au pseudo-code ci-dessous pour mieux le comprendre.

Procédure binary_search A & larr trié tableau n & larr taille du tableau x & larr valeur à rechercher Set low = 1 Set high = n tandis que x not found if high
 Explication: 
 
 
 Étape 1: Tout d'abord, comparez x avec l'élément du milieu.
 Étape 2: Si x correspond à l'élément du milieu, vous devez renvoyer l'index du milieu.
 Étape 3:  Sinon, si x est supérieur à l'élément central, alors x ne peut se trouver que dans le demi-tableau de droite après l'élément central. Par conséquent, vous répétez la moitié droite.
 Étape 4: Sinon, si (x est plus petit), alors se reproduit pour la moitié gauche.
C'est ainsi que vous devez rechercher l'élément dans le tableau donné.
comment créer un fichier journal en java
Voyons maintenant comment implémenter un algorithme de recherche binaire de manière récursive. Le programme ci-dessous démontre la même chose.
 Recherche binaire récursive 
public class BinarySearch {// Implémentation Java de la recherche binaire récursive // ​​Renvoie l'index de x s'il est présent dans arr [l..h], sinon retourne -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Si l'élément est présent au milieu lui-même if (a [mid] == x) return mid // Si élément est plus petit que mid, alors il ne peut être présent dans le sous-tableau de gauche que si (a [mid]> x) return binarySearch (arr, l, mid - 1, x) // Sinon, l'élément ne peut être présent que dans le sous-tableau de droite return binarySearch (arr, mid + 1, h, x)} // Nous arrivons ici lorsque l'élément n'est pas présent dans le tableau return -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a.length int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Élément non présent') else System.out.println ('Élément trouvé à l'index' + res)}}
Lors de l'exécution du programme ci-dessus, il localisera l'élément présent à l'index particulier
Élément trouvé à l'index 2
Cela nous amène donc à la fin de la recherche binaire dans Java article. J'espère que vous l'avez trouvé informatif et vous avez aidé à comprendre  .
 Vérifiez    par Edureka, une entreprise d'apprentissage en ligne de confiance avec un réseau de plus de 250 000 apprenants satisfaits répartis dans le monde entier. Nous sommes là pour vous aider à chaque étape de votre voyage, pour devenir une autre question d'entrevue java. Nous proposons un programme conçu pour les étudiants et les professionnels qui souhaitent devenir développeur Java. Le cours est conçu pour vous donner une longueur d'avance dans la programmation Java et vous former aux concepts Java de base et avancés ainsi qu'à divers frameworks Java tels que Hibernate & Spring. 
 Au cas où vous rencontriez des difficultés lors de la mise en œuvre de la recherche binaire dans  , merci de le mentionner dans la section commentaires ci-dessous  et nous vous répondrons au plus tôt.