Algorithme de recherche binaire (Binary Search) dans Java

L'algorithme de recherche binaire est une méthode efficace de Java programmation, utilisée pour trouver une valeur spécifique dans un tableau trié. Cette approche divise continuellement le tableau en deux parties et compare la valeur de recherche avec l'élément du milieu.

Comment fonctionne l'algorithme de recherche binaire

L'algorithme de recherche binaire commence par comparer la valeur de recherche avec l'élément central du tableau. Si la valeur de recherche est égale à l'élément du milieu, l'algorithme renvoie la position de cet élément. Si la valeur de recherche est inférieure à l'élément du milieu, l'algorithme poursuit la recherche dans la moitié gauche du tableau. Si la valeur de recherche est supérieure, l'algorithme poursuit la recherche dans la moitié droite du tableau. Ce processus se répète jusqu'à ce que la valeur recherchée soit trouvée ou qu'il n'y ait plus d'éléments à rechercher.

Avantages et inconvénients de l'algorithme de recherche binaire

Avantages:

• Haute efficacité : cet algorithme élimine la moitié des éléments à chaque étape, optimisant ainsi la recherche de grands tableaux.
• Faible complexité temporelle : la complexité temporelle de cet algorithme est O(log n), ce qui le rend efficace pour les grands ensembles de données.

Désavantages:

• Exigence relative aux tableaux triés : l'algorithme ne fonctionne qu'avec des tableaux triés.

Exemple et explication

Prenons un exemple d'utilisation de l'algorithme de recherche binaire pour trouver un entier spécifique dans un tableau d'entiers triés dans Java.

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}  

Dans cet exemple, nous utilisons l'algorithme de recherche binaire pour trouver le nombre 9 dans un tableau d'entiers triés. L'algorithme parcourt le tableau et compare la valeur de recherche avec la valeur médiane. Dans ce cas, le nombre 9 se trouve à la position 4(index basé sur 0) dans le tableau.

Bien que cet exemple montre comment l'algorithme de recherche binaire peut trouver un élément dans un tableau d'entiers triés, il peut également être appliqué à d'autres scénarios de recherche en Java programmation.