Worst Case für eine binäre Suche, wenn Sie nicht mit einer Potenz von 2 umgehen

Question

Ich verstehe, dass im schlimmsten Fall die Anzahl der Annahmen für eine binäre Suche ist lg (n) +1, wobei n die Anzahl der Elemente ist du suchst. Ich verstehe das vollständig, aber das gibt dir natürlich nur eine nette Zahl, wenn n eine Potenz von 2 ist. Wenn n keine Potenz von 2 ist, dann wird dir gesagt, dass du einfach zur nächsten Potenz von 2 gehst geh bis zu 8 dann lg (8) + 1 = 4. Aber wenn du mit 5 Elementen zu tun hättest, wäre der schlimmste Fall 3 Raten. Was vermisse ich?

Danke!

Answer 1

Die tatsächliche Formel Boden (log (N) + 1) (Basis-2 log Verwendung). So Boden (log (5) + 1) = Boden (2.x + 1) = Boden (3.x) = 3.