Recherche dichotomique itérative et récursive| Java

Dans ce tutoriel nous allons découvrir comment effectuer une recherche dichotomique de façon itérative et récursive en Java.

La recherche dichotomique est utilisée pour rechercher un élément à partir de plusieurs éléments. La recherche dichotomique est plus rapide que la recherche linéaire.

Dans la recherche dichotomique, les éléments du tableau doivent être dans l’ordre croissant. Si vous avez un tableau non trié, vous pouvez trier le tableau à l’aide de la méthode Arrays.sort(tableau).
 

 
 

Exemple 1: De façon itérative

public class BinarySearch{
  /*
	tab[] : le tableau dans lequel on va chercher la valeur
	l : dernier élément
	f : premier élément
	val : valeur à trouver
  */
  public static void binarySearch(int tab[], int f, int l, int val){
    int mid = (f + l)/2;
    while(f <= l){
      if (tab[mid] < val){
        f = mid + 1;   
      }else if(tab[mid] == val){
        System.out.println("L'élément se trouve à l'index: " + mid);
        break;
      }else{
         l = mid - 1;
      }
      mid = (f + l)/2;
   }
    if (f > l){
      System.out.println("L'élément n'existe pas!");
    }
   }
 
  public static void main(String args[]){
		int tab[] = {1, 2, 3, 4, 5, 6, 7};
		int val = 4;
		int l = tab.length-1;
		binarySearch(tab,0,l,val);	
  }
}

 
Sortie:

L'élément se trouve à l'index: 3

Exemple 2: En utilisant la récursivité

public class BinarySearch{
  /*
	tab[] : le tableau dans lequel on va chercher la valeur
	l : dernier élément
	f : premier élément
	val : valeur à trouver
  */
   public static int binarySearch(int tab[], int f, int l, int val){
		if (l >= f){
			int mid = f + (l - f)/2;
			if (tab[mid] == val){
				return mid;
			}
			if (tab[mid] > val){
				//recherche dans le sous-tableau à gauche
				return binarySearch(tab, f, mid-1, val); 
			}else{
				//recherche dans le sous-tableau à droit
				return binarySearch(tab, mid+1, l, val); 
			}
		}
		return -1;
   }
   public static void main(String args[]){
		int tab[] = {1, 2, 3, 4, 5, 6, 7};
		int val = 4;
		int l = tab.length-1;
		int res = binarySearch(tab,0,l,val);	
		if (res != -1)
			System.out.println("L'élément se trouve à l'index: " + res);
		else
			System.out.println("L'élément n'existe pas!");
   }
}

 
Sortie:

L'élément se trouve à l'index: 3