Java utilise la fonction binaireSearch() de la classe Collections pour effectuer une recherche binaire dans une collection ordonnée.

Java utilise la fonction binaireSearch() de la classe Collections pour effectuer une recherche binaire dans une collection ordonnée

La recherche binaire est un algorithme efficace pour trouver des éléments spécifiques dans une collection ordonnée. En Java, nous pouvons utiliser la fonction binaireSearch() de la classe Collections pour implémenter la recherche binaire. Cet article explique comment utiliser la fonction binaireSearch() pour effectuer une recherche dans une collection ordonnée et fournit des exemples de code spécifiques.

L'idée de base de l'algorithme de recherche binaire est de comparer l'élément à trouver avec l'élément du milieu de l'ensemble ordonné. Si l'élément du milieu est égal à l'élément à trouver, la recherche est réussie si l'élément du milieu ; L'élément du milieu est plus grand que l'élément à trouver, il est dans la moitié gauche de l'ensemble Continuer la recherche en partie ; si l'élément du milieu est plus petit que l'élément à trouver, continuer la recherche dans la moitié droite de l'ensemble. En réduisant continuellement la portée de la recherche, l'élément cible peut éventuellement être trouvé ou déterminé comme n'existant pas dans la collection.

En Java, nous pouvons utiliser la fonction binaireSearch() de la classe Collections pour implémenter la recherche binaire. La définition de cette fonction est la suivante :

public static int binaireSearch(List> list, T key)

Cette fonction accepte une collection ordonnée qui implémente l'interface Comparable et l'élément à être trouvé en tant que paramètres et renvoie la valeur d'index de l'élément dans la collection. Si l'élément n'existe pas dans la collection, un nombre négatif est renvoyé, c'est-à-dire la valeur négative de la position où l'élément doit être inséré moins un (c'est-à-dire - (position d'insertion + 1)).

Ce qui suit est un exemple de code pour la recherche binaire à l'aide de la fonction binaireSearch() de la classe Collections :

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearchExample {

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(3);
    list.add(5);
    list.add(7);
    list.add(9);

    int index = Collections.binarySearch(list, 5);
    if (index >= 0) {
        System.out.println("Element found at index " + index);
    } else {
        System.out.println("Element not found. Insertion point: " + (-(index + 1)));
    }
}

}

Dans le code ci-dessus, nous créons une ArrayList d'entiers, qui contient des entiers ordonnés. Nous avons appelé la fonction binaireSearch() de la classe Collections pour trouver la valeur d'index de l'élément 5 de la collection. Puisque l'élément existe dans la collection, la valeur d'index de l'élément est renvoyée. Finalement, nous imprimerons "Élément trouvé à l'index 2".

Si nous recherchons un élément dans l'ensemble qui n'existe pas, disons 4, nous obtiendrons un nombre négatif indiquant la position où l'élément doit être inséré. Dans le code ci-dessus, puisque 4 doit être inséré à l'index 1, le nombre négatif renvoyé est -(1+1)=-2. Après avoir exécuté le code, nous verrons la sortie "Élément introuvable. Point d'insertion : -2".

En utilisant la fonction binaireSearch() de la classe Collections, nous pouvons facilement effectuer une recherche binaire dans une collection ordonnée. La complexité temporelle de cet algorithme est O(logN), donc la recherche binaire présente une efficacité et des avantages élevés lors du traitement de données à grande échelle.

Résumé :
Cet article présente la méthode d'utilisation de la fonction binaireSearch() de la classe Collections pour effectuer une recherche binaire dans une collection ordonnée en Java. En utilisant cette fonction, nous pouvons trouver rapidement la position d'un élément spécifique dans la collection. J'espère que grâce à l'introduction et aux exemples de code de cet article, les lecteurs pourront maîtriser l'application et l'utilisation de l'algorithme de recherche binaire et améliorer leur efficacité et leurs compétences en programmation.

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!