Comment implémenter un algorithme de recherche binaire en utilisant Java

Comment implémenter un algorithme de recherche binaire en Java

L'algorithme de recherche binaire est une méthode de recherche efficace adaptée aux tableaux triés. Son idée de base est de restreindre continuellement la plage de recherche, de comparer la valeur de recherche avec les éléments du milieu du tableau et de décider s'il faut continuer la recherche dans la moitié gauche ou la moitié droite en fonction du résultat de la comparaison jusqu'à ce que l'élément cible soit trouvé ou la plage de recherche est réduite à vide.

Nous allons maintenant présenter en détail comment implémenter l'algorithme de recherche binaire en Java.

Étape 1 : implémenter la méthode de recherche binaire

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; //表示未找到目标元素
    }
}

Étape 2 : tester la méthode de recherche binaire

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; //已排序数组
        int target = 12; //要查找的目标元素
        int index = BinarySearch.binarySearch(arr, target);
        
        if (index != -1) {
            System.out.println("目标元素在数组中的位置为：" + index);
        } else {
            System.out.println("未找到目标元素");
        }
    }
}

Le code ci-dessus définit d'abord une classe BinarySearch, qui contient une méthode statique binarySearch est utilisé pour implémenter l'algorithme de recherche binaire. Dans la méthode <code>binarySearch, nous définissons deux pointeurs, left et right, pour pointer respectivement vers les éléments les plus à gauche et les plus à droite de la plage de recherche. Dans une boucle, l'index de l'élément du milieu mid est calculé puis la valeur de recherche est comparée à arr[mid]. Si les deux sont égaux, cela signifie que l'élément cible est trouvé et sa valeur d'index mid est renvoyée. Si la valeur de recherche est supérieure à arr[mid], déplacez le pointeur gauche d'une position vers la droite et réduisez la plage de recherche à la moitié droite. Si la valeur de recherche est inférieure à arr[mid], déplacez le pointeur droit d'une position vers la gauche pour réduire la plage de recherche à la moitié gauche. La boucle continue jusqu'à ce que l'élément cible soit trouvé ou que la plage de recherche soit vide. Si l'élément cible n'est pas trouvé à la fin de la boucle, -1 est renvoyé pour indiquer qu'il n'a pas été trouvé. BinarySearch类，其中包含了一个静态方法binarySearch用于实现二分查找算法。在binarySearch方法中，我们定义了left和right两个指针分别指向查找范围的最左和最右元素。在一个循环中，通过计算得到中间元素的索引mid，然后将查找值与arr[mid]进行比较。如果两者相等，则表示找到了目标元素，返回其索引值mid。如果查找值大于arr[mid]，则将left指针右移一位，缩小查找范围为右半部分。如果查找值小于arr[mid]，则将right指针左移一位，缩小查找范围为左半部分。循环继续直到找到目标元素或查找范围为空。如果循环结束后未找到目标元素，返回-1表示未找到。

在Main类的main方法中，我们创建了一个已排序的数组arr和一个待查找的目标元素target。然后调用BinarySearch类的binarySearch方法进行二分查找，将返回的结果存储在index

Dans la méthode main de la classe Main, on crée un tableau trié arr et un élément cible à trouver cible. Appelez ensuite la méthode <code>binarySearch de la classe BinarySearch pour effectuer une recherche binaire et stockez le résultat renvoyé dans la variable index. Enfin, il est jugé si l'élément cible est trouvé sur la base du résultat renvoyé, et le résultat correspondant est imprimé.

Grâce aux exemples de code ci-dessus, nous pouvons voir que la mise en œuvre de l'algorithme de recherche binaire en Java est très simple et ne nécessite que quelques lignes de code. Cette méthode a une complexité de temps de recherche de O(logn), ce qui est très efficace et adapté aux grands tableaux triés. Si plusieurs opérations de recherche sont nécessaires, l'opération de tri du tableau peut être divisée séparément pour améliorer l'efficacité.

J'espère que cet article vous aidera à comprendre et à utiliser l'algorithme de recherche binaire ! 🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!