Binäre Suche

In diesem Tutorial erfahren Sie, wie die Sortierung der binären Suche funktioniert. Außerdem finden Sie Arbeitsbeispiele für die binäre Suche in C, C ++, Java und Python.

Die binäre Suche ist ein Suchalgorithmus zum Finden der Position eines Elements in einem sortierten Array.

Bei diesem Ansatz wird das Element immer in der Mitte eines Teils eines Arrays gesucht.

Die binäre Suche kann nur für eine sortierte Liste von Elementen implementiert werden. Wenn die Elemente noch nicht sortiert sind, müssen wir sie zuerst sortieren.

Binäre Suche funktioniert

Der binäre Suchalgorithmus kann auf zwei Arten implementiert werden, die unten diskutiert werden.

  1. Iterative Methode
  2. Rekursive Methode

Die rekursive Methode folgt dem Divide and Conquer-Ansatz.

Die allgemeinen Schritte für beide Methoden werden unten diskutiert.

  1. Das Array, in dem gesucht werden soll, ist: Anfangsarray
    Sei x = 4das zu durchsuchende Element.
  2. Setzen Sie zwei Zeiger niedrig und hoch an der niedrigsten bzw. der höchsten Position. Zeiger setzen
  3. Finden Sie das mittlere Element in der Mitte des Arrays, dh. (arr(low + high)) / 2 = 6. Mittleres Element
  4. Wenn x == mid, dann return mid.Else, vergleiche das zu durchsuchende Element mit m.
  5. Wenn x> midja, vergleichen Sie x mit dem mittleren Element der Elemente auf der rechten Seite der Mitte. Dies erfolgt durch Einstellen von niedrig auf low = mid + 1.
  6. Andernfalls vergleichen Sie x mit dem mittleren Element der Elemente auf der linken Seite der Mitte. Dies erfolgt durch Einstellen von High auf high = mid - 1. Mittelelement finden
  7. Wiederholen Sie die Schritte 3 bis 6, bis niedrig auf hoch trifft. Mittleres Element
  8. x = 4gefunden. Gefunden

Binärer Suchalgorithmus

Iterationsmethode

tun, bis sich die Zeiger niedrig und hoch treffen. mid = (low + high) / 2 if (x == arr (mid)) return mid else if (x> A (mid)) // x ist auf der rechten Seite low = mid + 1 else // x ist on die linke Seite hoch = Mitte - 1

Rekursive Methode

 binarySearch (arr, x, niedrig, hoch) wenn niedrig> hoch return False else mid = (niedrig + hoch) / 2 wenn x == arr (mid) return mid else wenn x <data (mid) // x auf dem ist rechte Seite return binarySearch (arr, x, mid + 1, high) sonst // x ist auf der rechten Seite return binarySearch (arr, x, niedrig, mid - 1)

Beispiele für Python, Java, C / C ++ (iterative Methode)

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); )

Beispiele für Python, Java, C / C ++ (rekursive Methode)

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); )

Komplexität der binären Suche

Zeitliche Komplexität

  • Best-Case-Komplexität :O(1)
  • Durchschnittliche Fallkomplexität :O(log n)
  • Worst-Case-Komplexität :O(log n)

Raumkomplexität

Die räumliche Komplexität der binären Suche ist O(n).

Binäre Suchanwendungen

  • In Bibliotheken von Java, .Net, C ++ STL
  • Während des Debuggens wird die binäre Suche verwendet, um den Ort zu bestimmen, an dem der Fehler auftritt.

Interessante Beiträge...