Comment implémenter la recherche binaire en Java ?

Il existe deux façons d’effectuer une recherche binaire en Java.

1.Arrays.binarysearch()S'applique aux tableaux qui peuvent également être des types de données primitifs.

import java.util.Arrays; 
  
public class GFG { 
    public static void main(String[] args) 
    { 
        int arr[] = { 10, 20, 15, 22, 35 }; 
        Arrays.sort(arr); 
  
        int key = 22; 
        int res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 40; 
        res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

Sortie :

22 found at index = 3
40 Not found

2.Collections.binarysearch()Applicable aux collections d'objets, telles que ArrayList et LinkedList.

import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 
   
public class GFG 
{ 
    public static void main(String[] args) 
    { 
        List<Integer> al = new ArrayList<Integer>(); 
        al.add(1); 
        al.add(2); 
        al.add(3); 
        al.add(10); 
        al.add(20); 
   
        int key = 10; 
        int res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                 + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 15; 
        res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = "
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

Sortie :

10 found at index = 3
15 Not found

Que faire si l'entrée n'est pas triée ?
Si la liste d'entrée n'est pas triée, le résultat est indéfini.

Et s'il y a des doublons ?
S'il y a des doublons, il n'y a aucune garantie lequel sera trouvé.

Comment Collections.binarySearch fonctionne-t-il pour LinkedList ?
Cette méthode s'exécute en temps log(n) et est utilisée pour les listes à « accès aléatoire » telles que ArrayList. Si la liste spécifiée n’implémente pas l’interface RandomAccess et est volumineuse, cette méthode effectue une recherche binaire basée sur un itérateur qui effectue une traversée de lien O(n) et une comparaison d’éléments O(log n).

Quelle est la signification des valeurs négatives renvoyées par les deux fonctions ?
Cette fonction renvoie l'index de la clé de recherche (si elle est contenue dans le tableau sinon, (- (point d'insertion) - 1). Le point d'insertion est défini comme le point auquel la clé sera insérée dans le tableau : l'index du premier élément est supérieur à la clé, ou a.length si tous les éléments du tableau sont inférieurs à la clé spécifiée. Notez que cela garantit une valeur de retour >= 0 si et seulement si la clé est trouvée.

Comment implémenter notre propre recherche binaire en Java ?

class BinarySearch 
{ 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r>=l) 
        { 
            int mid = l + (r - l)/2; 
            if (arr[mid] == x) 
               return mid; 

            if (arr[mid] > x) 
               return binarySearch(arr, l, mid-1, x); 
 
            return binarySearch(arr, mid+1, r, x); 
        } 

        return -1; 
    } 
 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = {2,3,4,10,40}; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr,0,n-1,x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " +  
                                                 result); 
    } 
}

Sortie :

Element found at index 3

Recommandations associées : "Tutoriel Java"

Cet article concerne l'implémentation binaire Java. La méthode de recherche est introduite, j'espère qu'elle sera utile aux amis qui en ont besoin !

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!