Recherche binaire en Java : collections récursives, itératives et Java

La recherche linéaire en Java a toujours été la méthode de référence pour rechercher un élément dans un tableau. Il recherche chaque élément du tableau de manière séquentielle et est extrêmement facile à mettre en œuvre. Cependant, les lacunes de la recherche linéaire sont évidentes lorsque le tableau en question contient des dizaines de milliers d'éléments. Dans de tels cas, la méthode «diviser pour régner» mise en œuvre par Binary Search est beaucoup plus efficace et préférable pour les programmeurs soucieux de la complexité temporelle et spatiale.

Recherche binaire

Dans la recherche binaire, un tableau est divisé à plusieurs reprises en deux moitiés jusqu'à ce que la clé (l'élément recherché) soit trouvée. La division est virtuelle c'est-à-dire que l'intégrité des données est maintenue. À chaque itération, la valeur médiane du tableau est focalisée. Si la valeur est égale à la clé que nous recherchons, la boucle ou la fonction récursive se termine. Sinon, il continue de tourner en boucle. Si la valeur médiane est supérieure à la clé, la fonction se concentre alors sur la première moitié du tableau et vice versa. Ce processus est répété jusqu'à ce que la clé soit trouvée ou que le tableau entier ait été itéré.

Différence entre la recherche linéaire et binaire

Algorithme de recherche binaire

L'algorithme de recherche binaire est donné ci-dessous.

1. Déterminez le premier et le dernier point du tableau. Les points seront ajustés à chaque itération selon le tableau et la clé recherchés.
2. Parcourez le tableau et comparez la valeur médiane entre vos premier et dernier points actuels. Dans la première itération, la première et la dernière variable seront les mêmes que celles réelles du tableau.
3. Si la clé est supérieure à la valeur médiane, l'indice de cette valeur sera stocké dans la nouvelle variable "Premier".
4. Si la clé est inférieure à la valeur médiane, l'index de cette valeur sera stocké dans la variable 'Last'.
5. Cette condition est répétée jusqu'à ce que l'une des deux conditions devienne vraie :
   • La clé est trouvée.
   • L'ensemble du tableau a été itéré.

Le code pour la recherche binaire itérative et la recherche binaire récursive est donné ci-dessous.

Recherche binaire itérative

Le code pour la recherche binaire avec une méthode itérative est donné ci-dessous.

import java.util.Scanner;
public class IterativeBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
       
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
       
        int num = input.nextInt();
        int result = BinarySearchIterative(arr,num);
       
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
    public static int BinarySearchIterative(int[] arr, int num){
        //Representing the Start and End Index After Division of Array
        int start = 0;
        int end = arr.length;
 
        //Loop to Iterate Through the Array
        for(int i = 0; iarr[n]){
                start = n;
            }
            //If number to search for is greater than the arr value at index 'n'               
            else{
                end = n;
            }
        }
        //If number isn't found, return -1
        return -1;
    }
}

Recherche binaire récursive

Le code pour Binary utilisant la récursivité est donné ci-dessous.

import java.util.Scanner;
public class RecursiveBinarySearch {
 
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,10};
 
        System.out.println("Enter Number to Search For: ");
        Scanner input = new Scanner (System.in);
 
        int num = input.nextInt();
        int result = BinarySearchRecursive(arr,0,arr.length-1,num);
 
        if(result!=-1)
            System.out.println("Value Found at Index #" + result);
        else
            System.out.println("Value Not Found");
    }
 
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
    //Base Case to Exit the Recursive Function
    if (b < 1) {
        return -1;
    }
        int n = a + (b=1)/2;
 
       //If number is found at mean index of start and end
        if(arr[n]==num)
            return n;
 
       //If number to search for is greater than the arr value at index 'n'
        else if(arr[n]>num)
            return BinarySearchRecursive(arr,a,n-1,num);
 
       //If number to search for is greater than the arr value at index 'n'
        else
            return BinarySearchRecursive(arr,n+1,b,num);
    }
 
}

Complexité temporelle

À chaque itération qui passe, le tableau, c'est-à-dire l'espace de recherche, est divisé en deux. Après chaque itération 'm', l'espace de recherche passera à une taille de N/2m. Dans le pire des cas, il ne nous restera qu'un seul élément d'un côté éloigné du tableau. À ce moment, la complexité de la recherche binaire sera k = log2N. La complexité temporelle de la recherche linéaire est O(N) ce qui fait que la recherche binaire est beaucoup plus rapide avec la complexité O(log2N). C'est le principal avantage de l'utilisation de la recherche binaire par rapport à la recherche linéaire.

Complexité spatiale

La recherche binaire utilise trois variables différentes : début, fin et milieu. Ces trois variables sont créées sous forme de pointeurs qui pointent vers l'emplacement mémoire des indices du tableau. Pour cette raison, la recherche binaire est extrêmement efficace avec de l'espace. La complexité spatiale de la recherche binaire itérative est O(1). Pour une implémentation récursive, c'est O(log N).