Recherche binaire

Dans ce didacticiel, vous apprendrez comment fonctionne le tri par recherche binaire. Vous trouverez également des exemples fonctionnels de recherche binaire en C, C ++, Java et Python.

La recherche binaire est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié.

Dans cette approche, l'élément est toujours recherché au milieu d'une partie d'un tableau.

La recherche binaire ne peut être implémentée que sur une liste triée d'éléments. Si les éléments ne sont pas déjà triés, nous devons d'abord les trier.

Recherche binaire fonctionnant

L'algorithme de recherche binaire peut être implémenté de deux manières décrites ci-dessous.

  1. Méthode itérative
  2. Méthode récursive

La méthode récursive suit l'approche diviser pour conquérir.

Les étapes générales des deux méthodes sont décrites ci-dessous.

  1. Le tableau dans lequel la recherche doit être effectuée est: Tableau initial
    Soit x = 4l'élément à rechercher.
  2. Définissez deux pointeurs bas et haut respectivement aux positions la plus basse et la plus élevée. Réglage des pointeurs
  3. Trouvez l'élément central au milieu du tableau, c'est-à-dire. (arr(low + high)) / 2 = 6. Élément intermédiaire
  4. Si x == mid, alors renvoie mid.Else, comparez l'élément à rechercher avec m.
  5. Si x> mid, comparez x avec l'élément central des éléments sur le côté droit du milieu. Cela se fait en réglant bas sur low = mid + 1.
  6. Sinon, comparez x avec l'élément central des éléments sur le côté gauche du milieu. Cela se fait en réglant sur high = mid - 1. Recherche de l'élément central
  7. Répétez les étapes 3 à 6 jusqu'à ce que le bas rencontre le haut. Élément intermédiaire
  8. x = 4est trouvé. A trouvé

Algorithme de recherche binaire

Méthode d'itération

faites jusqu'à ce que les pointeurs bas et haut se rencontrent. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x est sur le côté droit low = mid + 1 else // x est activé le côté gauche haut = milieu - 1

Méthode récursive

 binarySearch (arr, x, low, high) if low> high return False else mid = (low + high) / 2 if x == arr (mid) return mid else si x <data (mid) // x est sur le côté droit return binarySearch (arr, x, mid + 1, high) else // x est sur le côté droit return binarySearch (arr, x, low, mid - 1)

Exemples Python, Java, C / C ++ (méthode itérative)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Exemples Python, Java, C / C ++ (méthode récursive)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Complexité de la recherche binaire

Complexités temporelles

  • Meilleure complexité des cas :O(1)
  • Complexité moyenne des cas :O(log n)
  • Pire complexité des cas :O(log n)

Complexité spatiale

La complexité spatiale de la recherche binaire est O(n).

Applications de recherche binaire

  • Dans les bibliothèques de Java, .Net, C ++ STL
  • Pendant le débogage, la recherche binaire est utilisée pour identifier l'endroit où l'erreur se produit.

Articles intéressants...