Recherche dichotomique en Java

Introduction

La recherche dichotomique est un algorithme de recherche efficace utilisé pour trouver une valeur dans un tableau trié. Elle est plus rapide que la recherche linéaire car elle élimine la moitié du tableau à chaque itération. Dans ce laboratoire, nous allons apprendre les étapes pour implémenter l'algorithme de recherche dichotomique en Java.

Skills Graph

Créer un tableau trié

L'algorithme de recherche dichotomique nécessite un tableau trié, nous allons donc tout d'abord créer un tableau trié.

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

Implémenter la recherche dichotomique de manière itérative

Nous allons maintenant implémenter l'algorithme de recherche dichotomique de manière itérative. Cette méthode renvoie l'index de l'élément s'il est présent dans le tableau. Sinon, elle renvoie -1.

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

Pour exécuter le code, nous devons tout d'abord appeler la méthode binarySearchIterative, en passant sortedArray et l'élément que nous voulons rechercher en tant que paramètres.

## compiler le fichier java
javac BinarySearch.java

## exécuter le fichier
java BinarySearch

Implémenter la recherche dichotomique de manière récursive

Nous allons maintenant implémenter l'algorithme de recherche dichotomique de manière récursive. Cette méthode renvoie également l'index de l'élément s'il est présent dans le tableau. Sinon, elle renvoie -1.

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

Pour exécuter le code, nous devons appeler la méthode binarySearchRecursive, en passant sortedArray, l'élément que nous voulons rechercher, leftIdx et rightIdx en tant que paramètres.

Utiliser des méthodes intégrées pour la recherche dichotomique

Java dispose également de fonctions intégrées pour implémenter la recherche dichotomique. Ces fonctions sont Arrays.binarySearch() et Collections.binarySearch(). Nous pouvons utiliser ces fonctions pour rechercher un élément dans un tableau trié.

La fonction Arrays.binarySearch() prend un tableau trié et une valeur clé à rechercher en tant que paramètres. La fonction renvoie l'index de la clé si elle est présente dans le tableau. Sinon, elle renvoie -1.

int index = Arrays.binarySearch(sortedArray, 6);

La fonction Collections.binarySearch() peut être utilisée sur des collections telles que les ArrayLists pour rechercher un élément. La fonction prend la collection triée et une clé en tant que paramètres et renvoie l'index auquel la clé est présente. Sinon, elle renvoie -1.

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

Test

Nous allons maintenant tester toutes les méthodes et afficher la sortie.

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}

Pour exécuter le code, nous compilons tout d'abord le programme Java.

javac BinarySearch.java

Ensuite, nous pouvons exécuter le programme.

java BinarySearch

Résumé

Ce laboratoire a couvert les étapes nécessaires pour implémenter l'algorithme de recherche dichotomique de manière itérative et récursive dans le langage de programmation Java. Nous avons également appris sur les méthodes intégrées Arrays.binarySearch() et Collections.binarySearch() pour implémenter la recherche dichotomique. Nous avons créé un tableau trié et utilisé différentes méthodes pour rechercher des éléments dans celui-ci.