Wie ist die binäre Suche im Vergleich zu anderen Suchverfahren?
How is binary search vs other searching schemes?
Sorted arrays with the binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval. In addition, sorted arrays can complicate memory use especially when elements are often inserted into the array.
Binary search is faster than linear search for sorted arrays except if the array is short, although the array needs to be sorted beforehand.
Binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search.
a data structure that maps keys to records using a hash function, is generally faster than binary search on a sorted array of records.
Sortierte Arrays mit der binären Suche sind eine sehr ineffiziente Lösung, wenn Einfüge- und Löschvorgänge mit Abrufen verschachtelt werden. Außerdem können sortierte Arrays die Speichernutzung erschweren, vor allem wenn häufig Elemente in das Array eingefügt werden.
Die binäre Suche ist bei sortierten Arrays schneller als die lineare Suche, es sei denn, das Array ist kurz, obwohl das Array vorher sortiert werden muss.
Die binäre Suche ist in der Regel effizienter, da binäre Suchbäume höchstwahrscheinlich nicht perfekt ausbalanciert sind, was zu einer etwas schlechteren Leistung als die binäre Suche führt.
Eine Datenstruktur, die Schlüssel mithilfe einer Hash-Funktion auf Datensätze abbildet, ist in der Regel schneller als die binäre Suche in einem sortierten Array von Datensätzen.
summarization
Sortierte Arrays mit binärer Suche sind eine sehr ineffiziente Lösung, wenn Einfüge- und Löschvorgänge mit dem Abruf verschachtelt werden, so dass

O(n) Zeit für jede dieser Operationen. Außerdem können sortierte Arrays die Speichernutzung erschweren, vor allem wenn häufig Elemente in das Array eingefügt werden. Es gibt andere Datenstrukturen, die das Einfügen und Löschen von Elementen viel effizienter machen. Die binäre Suche kann verwendet werden, um exakte Übereinstimmungen und die Zugehörigkeit zu einer Menge zu ermitteln (ob ein Zielwert in einer Sammlung von Werten enthalten ist). Es gibt Datenstrukturen, die einen schnelleren exakten Abgleich und Mengenzugehörigkeit unterstützen. Im Gegensatz zu vielen anderen Suchverfahren kann die binäre Suche jedoch auch für eine effiziente ungefähre Übereinstimmung verwendet werden.
O(log n)-Zeit durchführen, unabhängig von der Art oder Struktur der Werte selbst. Darüber hinaus gibt es einige Operationen, wie z. B. die Suche nach dem kleinsten und größten Element, die mit einem sortierten Array effizient durchgeführt werden können.

Lineare Suche:

Die lineare Suche ist ein einfacher Suchalgorithmus, der jeden Datensatz überprüft, bis er den Zielwert findet. Die lineare Suche kann in einer verknüpften Liste durchgeführt werden, die ein schnelleres Einfügen und Löschen ermöglicht als ein Array. Die binäre Suche ist bei sortierten Arrays schneller als die lineare Suche, es sei denn, das Array ist kurz, obwohl das Array vorher sortiert werden muss. Alle Sortieralgorithmen, die auf dem Vergleich von Elementen basieren, wie Quicksort und Merge Sort, benötigen mindestens
O(nlog n) Vergleiche im schlimmsten Fall. Im Gegensatz zur linearen Suche kann die binäre Suche für einen effizienten Näherungsabgleich verwendet werden. Es gibt Operationen wie die Suche nach dem kleinsten und dem größten Element, die bei einem sortierten Array effizient durchgeführt werden können, aber nicht bei einem unsortierten Array.

Bäume:

Binäre Suchbäume werden mit einem Algorithmus durchsucht, der der binären Suche ähnelt.
Ein binärer Suchbaum ist eine binäre Baumdatenstruktur, die nach dem Prinzip der binären Suche funktioniert. Die Datensätze des Baums sind in sortierter Reihenfolge angeordnet, und jeder Datensatz im Baum kann mit einem der binären Suche ähnlichen Algorithmus durchsucht werden, der im Durchschnitt logarithmische Zeit benötigt. Auch das Einfügen und Löschen von Datensätzen benötigt in binären Suchbäumen im Durchschnitt logarithmische Zeit. Das kann schneller sein als das Einfügen und Löschen in linearer Zeit bei sortierten Arrays. Außerdem können binäre Bäume alle Operationen durchführen, die bei einem sortierten Array möglich sind, einschließlich Bereichsabfragen und Näherungsabfragen.

Allerdings ist die binäre Suche in der Regel effizienter für die Suche, da binäre Suchbäume höchstwahrscheinlich nicht perfekt ausbalanciert sind, was zu einer etwas schlechteren Leistung als die binäre Suche führt. Das gilt sogar für balancierte binäre Suchbäume, d. h. binäre Suchbäume, die ihre eigenen Knoten ausbalancieren, da sie selten den Baum mit den wenigsten Ebenen erzeugen. Außer bei balancierten binären Suchbäumen kann der Baum stark unausgewogen sein und nur wenige interne Knoten mit zwei Kindern haben, was dazu führt, dass die durchschnittliche und schlimmste Suchzeit bei
n Vergleiche. Binäre Suchbäume benötigen mehr Platz als sortierte Arrays.

Binäre Suchbäume eignen sich für die schnelle Suche im externen Speicher auf Festplatten, da binäre Suchbäume in Dateisystemen effizient strukturiert werden können. Der B-Baum verallgemeinert diese Methode der Baumorganisation. B-Bäume werden häufig verwendet, um Langzeitspeicher wie Datenbanken und Dateisysteme zu organisieren.

Hashing:
Für die Implementierung von assoziativen Arrays sind Hash-Tabellen, eine Datenstruktur, die Schlüssel mithilfe einer Hash-Funktion auf Datensätze abbildet, in der Regel schneller als die binäre Suche in einem sortierten Array von Datensätzen. Die meisten Hash-Tabellen-Implementierungen benötigen im Durchschnitt nur eine amortisierte konstante Zeit. Die binäre Suche ist ideal für solche Übereinstimmungen, da sie in logarithmischer Zeit durchgeführt werden kann. Die binäre Suche unterstützt auch ungefähre Übereinstimmungen. Einige Operationen, wie die Suche nach dem kleinsten und dem größten Element, können effizient mit sortierten Arrays durchgeführt werden, nicht aber mit Hashtabellen.

Algorithmen zur Mengenzugehörigkeit:
Ein ähnliches Problem wie die Suche ist die Mengenzugehörigkeit. Jeder Algorithmus, der Nachschlageoperationen wie die binäre Suche durchführt, kann auch für die Mengenzugehörigkeit verwendet werden. Es gibt noch andere Algorithmen, die speziell für die Mengenzugehörigkeit geeignet sind. Ein Bit-Array ist der einfachste und nützlich, wenn der Bereich der Schlüssel begrenzt ist. Es speichert kompakt eine Sammlung von Bits, wobei jedes Bit einen einzelnen Schlüssel innerhalb des Schlüsselbereichs darstellt. Bit-Arrays sind sehr schnell und benötigen nur
Der Typ Judy1 des Judy-Arrays kann 64-Bit-Schlüssel effizient verarbeiten.

Für ungefähre Ergebnisse speichern Bloom-Filter, eine weitere probabilistische Datenstruktur, die auf Hash-Funktionen basiert, einen Satz von Schlüsseln, indem sie die Schlüssel mit einem Bit-Array und mehreren Hash-Funktionen kodieren. Bloom-Filter sind in den meisten Fällen viel platzsparender als Bit-Arrays und nicht viel langsamer: Mit
k Hash-Funktionen benötigen Mitgliederabfragen nur
 O(k) Zeit. Allerdings leiden Bloom-Filter unter falsch-positiven Ergebnissen.

Andere Datenstrukturen:
Es gibt Datenstrukturen, die die binäre Suche in einigen Fällen sowohl bei der Suche als auch bei anderen Operationen für sortierte Arrays verbessern können. Zum Beispiel können Suchvorgänge, ungefähre Übereinstimmungen und die für sortierte Arrays verfügbaren Operationen mit spezialisierten Datenstrukturen wie van Emde Boas-Bäumen, Fusionsbäumen, Tries und Bit-Arrays effizienter durchgeführt werden als mit der binären Suche. Diese spezialisierten Datenstrukturen sind in der Regel nur deshalb schneller, weil sie sich die Eigenschaften von Schlüsseln mit einem bestimmten Attribut zunutze machen (in der Regel Schlüssel, die kleine ganze Zahlen sind) und daher für Schlüssel, die dieses Attribut nicht haben, zeit- oder platzraubend sind. Solange die Schlüssel geordnet werden können, können diese Operationen unabhängig von den Schlüsseln immer mindestens effizient mit einem sortierten Array durchgeführt werden. Einige Strukturen, wie z. B. Judy-Arrays, verwenden eine Kombination aus verschiedenen Ansätzen, um dieses Problem zu lösen und gleichzeitig die Effizienz und die Fähigkeit, eine ungefähre Zuordnung vorzunehmen, zu bewahren.
de