Ist es möglich, bei einem binären Suchalgorithmus nur einen Vergleich pro Iteration durchzuführen?

Question

Beim binären Suchalgorithmus gibt es zwei Vergleiche:

if (key == a[mid]) then found;

else if (key < a[mid]) then binary_search(a[],left,mid-1);
      else binary_search(a[],mid+1,right);

Gibt es einen Weg, wie ich nur einen Vergleich anstelle der beiden oben genannten durchführen kann?

--

Gracias

Alok.Kr.

Answer 1

Siehe:

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

Entnommen aus wiki:

   low = 0
   high = N
   while (low < high) {
       mid = low + ((high - low) / 2)
       if (A[mid] < value)
           low = mid + 1;
       else
            //can't be high = mid-1: here A[mid] >= value,
            //so high can't be < mid if A[mid] == value
            high = mid;
   }
   // high == low, using high or low depends on taste
   if ((low < N) && (A[low] == value))
       return low // found
   else
       return -1 // not found

Vor- und Nachteile aus dem Wiki: "Dieser Ansatz verzichtet auf die Möglichkeit eines vorzeitigen Abbruchs bei der Entdeckung einer Übereinstimmung, so dass erfolgreiche Suchen log2(N) Iterationen statt der erwarteten log2(N) 1 Iterationen aufweisen. Andererseits führt diese Implementierung weniger Vergleiche durch: log2(N) ist weniger als die erwartete Anzahl von Vergleichen für die zwei Testimplementierungen von 1-5(log2(N) 1), für N größer als acht."

Answer 2

Ja. Eliminieren Sie nur nicht mid aus dem rekursiven Aufruf.

if ( left == right ) return NULL;
if ( left + 1 == right ) return key == a[left]? &a[left] : NULL;

mid = left + ( right - left / 2 );

if (key < a[mid]) return binary_search(a[],left,mid-1);
else return binary_search(a[],mid,right); // include `mid` in next round

Sie müssen bei jeder Rekursion nur die Hälfte der Menge eliminieren, um eine Leistung von O(logN) zu erreichen. Mit der Eliminierung der Hälfte+1 gehen Sie weit darüber hinaus.

Wenn Sie nur < während der Rekursion findet der Algorithmus das kleinste Element, das nicht kleiner ist als key (kann aber größer sein als key ). Führen Sie abschließend einen einzigen Gleichheitstest durch.

Answer 3

In Assembler könnten Sie das:

cmp key,a[mid]
beq found
bge else

Wenn Ihr Compiler also wirklich gut bei der Peephole-Optimierung ist, könnte er dies bereits für Sie tun.

Answer 4

Dies ist ein rekursiver Algorithmus. Der erste Vergleich ist ein Stoppkriterium und der zweite die eigentliche Suche, daher können Sie diese nicht entfernen.

Erstens fragen Sie, wann Sie das Element bereits gefunden haben, und zweitens, in welchem Teil des Arrays Sie nach dem Element suchen müssen. Sie können diese Entscheidungen also nicht nur auf der Grundlage eines einzigen Vergleichs treffen.

Answer 5

Das Wichtigste zuerst: Müssen Sie das Programm optimieren? Haben Sie gemessen, um zu wissen, wo Sie es tun müssen? Ist es in dieser Funktion?

Bei primitiven Typen ist der zweite Vergleich die schnellste Operation, die es gibt. Die höheren Kosten des Vergleichs bestehen darin, das Element in das entsprechende Register zu laden, und das wird für den ersten Vergleich benötigt. Sobald dieser Vergleich ausgeführt ist, befindet sich der Wert bereits in einem Register, und die zweite Operation erfordert eine einzige Prozessoranweisung plus die möglichen Kosten für die Fehlvorhersage der Verzweigung.

Geht man von ganzzahligen Typen aus, so werden die Kosten für die Prozessorzeit des Algorithmus höchstwahrscheinlich von den Kosten der rekursiven Aufrufe dominiert, wenn der Compiler keine Tail-Recursion-Optimierung durchführen kann. Wenn Sie dies wirklich optimieren müssen, versuchen Sie, mit allen Optimierungsflags zu kompilieren, und analysieren Sie den Assembler, um festzustellen, ob die Tail-Recursion-Optimierung angewendet wird. Falls nicht, wandeln Sie den Algorithmus manuell von rekursiv in iterativ um.

Dies hat zwei Auswirkungen: Der Code wird unkenntlich gemacht (vermeiden Sie es, eine saubere Lösung zu ändern, wenn es nicht unbedingt notwendig ist) und es werden Funktionsaufrufe vermieden.

Wenn es sich um C++ handelt und der Typ komplex ist und die überladenen Vergleichsoperatoren teuer sind, ist die schnellste Leistungssteigerung die Implementierung einer compare Methode, die eine negative Zahl zurückgibt für weniger als , 0 für gleich, und eine positive Zahl, wenn größer-als . Dann wird das Ergebnis vor den Vergleichen vorberechnet und dann werden nur ganzzahlige Prüfungen durchgeführt. Das wird die Gesamtkosten des Algorithmus auf eine einzige Verarbeitung der realen Objekte mit dem teuren Vergleich reduzieren und Sie in die ursprüngliche Annahme zurückversetzen.