Recherche dichotomique Java interactive et récursive

  2. HowTo
  3. Howtos de Java
  4. Recherche dichotomique Java interactive …
Harshit Jindal 12 octobre 2023
Java Java Algorithm
  1. Algorithme de Recherche dichotomique itérative
  2. Programme itératif Java pour la Recherche dichotomique
  3. Algorithme de Recherche dichotomique récursive
  4. Programme récursif Java pour la Recherche dichotomique
  5. Arrays.binarySearch() Présentation
  6. Programme Java pour la Recherche dichotomique
Recherche dichotomique Java interactive et récursive
Noter
Si vous souhaitez comprendre la Recherche dichotomique en détail, consultez l’article algorithme de Recherche dichotomique.

Algorithme de Recherche dichotomique itérative

Supposons que nous ayons un tableau non trié A[] contenant n éléments, et nous voulons trouver un élément X.

  • Définissez lo sur 0 et hi sur n - 1.
  • Pendant que lo < hi:
    • Réglez mid = lo + (hi - lo)/2.
    • Si A[mid] == X, nous avons trouvé que l’élément renvoie l’index mid.
    • Si A[mid] < X, alors supprimez la moitié gauche des éléments et définissez lo sur mid+1.
    • Sinon si A[mid] > X, alors supprimez la moitié droite des éléments et définissez hi comme mid-1.
  • L’élément est introuvable, renvoyez donc -1.

Programme itératif Java pour la Recherche dichotomique

class BinarySearch {
  int binarySearch(int arr[], int x) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;

      if (arr[mid] == x)
        return mid;

      if (arr[mid] < x)
        lo = mid + 1;

      else
        hi = mid - 1;
    }
    return -1;
  }

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

Production:

Element found at index: 4

Algorithme de Recherche dichotomique récursive

Supposons que nous ayons un tableau non trié A[] contenant n éléments, et nous voulons trouver un élément X.

  • Initialise lo en tant que 0 et hi en tant que n-1.
  • si lo> hi, nous avons épuisé l’espace de recherche du tableau, retourne -1.
  • Calculez le point médian mid comme lo+(hi-lo)/2. Il divise le tableau en deux parties: la moitié inférieure avec des éléments de 0 à mid - 1 et la moitié supérieure avec des éléments de mid à n - 1.
  • Si X == mid, nous avons trouvé l’élément cible renvoyant mid.
  • Si X est inférieur à mid, recherchez la moitié inférieure du tableau en appelant récursivement binarysearch(arr, lo, mid-1).
  • Sinon, si X est supérieur à mid, recherchez la moitié supérieure du tableau en appelant récursivement binarysearch(arr, mid+1, hi).

Programme récursif Java pour la Recherche dichotomique

class BinarySearch {
  int binarySearch(int arr[], int lo, int hi, int x) {
    if (hi >= lo && lo < arr.length - 1) {
      int mid = lo + (hi - lo) / 2;
      if (arr[mid] == x)
        return mid;
      if (arr[mid] > x)
        return binarySearch(arr, lo, mid - 1, x);
      return binarySearch(arr, mid + 1, hi, x);
    }
    return -1;
  }
  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {1, 2, 3, 4, 5};
    int n = arr.length;
    int x = 2;
    int position = ob.binarySearch(arr, 0, n - 1, x);
    if (position == -1)
      System.out.println("Element not found !!!");
    else
      System.out.println("Element found at index: " + position);
  }
}

Production:

Element found at index: 1

Arrays.binarySearch() Présentation

Java nous fournit une fonction prête à l’emploi Arrays.binarySearch() afin que nous n’ayons pas à implémenter la fonction nous-mêmes. C’est une méthode très simple à utiliser et mise en œuvre efficacement et elle n’est pas sujette aux erreurs.

Syntaxe

public static int binarySearch(T arr, T key)

T peut être l’un des suivants: int, float, short, long, byte, char, double, et même un Object défini par l’utilisateur.

Tout comme notre Recherche dichotomique implémentée, elle nécessite également le tri du tableau, sinon les résultats ne sont pas définis. Il recherche le tableau en utilisant l’algorithme de Recherche dichotomique et trouve l’index de l’élément cible. S’il existe plusieurs occurrences de l’élément cible, il peut renvoyer l’index de l’un d’entre eux.

Paramètres
Arr Le tableau d’entrée
Key L’élément cible que nous recherchons.

Retourne

S’il trouve l’élément cible, il renvoie son index. Sinon, il renvoie beg - 1 où beg est l’index de départ de l’espace de recherche du tableau.

Programme Java pour la Recherche dichotomique

import java.util.Arrays;

class BinarySearchExample {
  public static void main(String args[]) {
    int arr[] = {1, 2, 3, 4, 5};
    int key = 2;
    int result = Arrays.binarySearch(arr, key);
    if (result < 0)
      System.out.println("Element is not found!");
    else
      System.out.println("Element is found at index: " + result);
  }
}

Production:

Element is found at index: 1
Auteur: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn