二進制搜索的最差情況時間複雜度

Question

衆所周知，對於大小爲n的排序數組，最差情況下的二進制搜索需要t個時間單位。如果輸入大小爲n/2，算法在最壞的情況下會花多長時間？

Answer 1

我們的新輸入與原始輸入的差異因數爲2.因爲二進制搜索的最壞情況時間已知具有對數複雜度，所以時間的漸近上界應該是相同的。這應該適用於任何原始數量爲2的倍數的輸入。