二進制搜索的比較次數的復發關係

Question

對二進制搜索中的比較次數的復發關係有疑問。

我讀到復發者可= T（N/2）+ 1在該網站http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L14-RecRel.htm

根據我應該是T（N）= T（N/2）寫爲T（n）的+ 2，因爲在最壞的情況下，元素可能不會出現在數組中，我們最終在每次傳遞中進行2次比較。

請告訴我我是對還是錯。

Answer 1

我認爲你是對的。

恕我直言，compare a b表示我們知道a=b,a>b或a<b在同一時間。也就是說，1個比較可能有3個不同的結果。

但是對於編程語言。我們必須使用2個比較。

if mid == x:  found it!   # 1st 
else if mid < x: search right  # 2nd 
else:    search left 

你指的是==和< 2個比較。

雖然它不影響結果。因爲我們使用大O符號來表示複雜性。這只是一個不變的問題，但O通常不關心它。

根據master theorem。 +1或+2將導致相同的複雜性O(log n)。

我們想要的通常是一個極限（Big-O），而不是一個數學方程的精確結果。

我認爲這裏重要的是1和2都是恆定時間。我們也可以將==,>分成機器說明，它可能會大於2。或者，也許一些編程語言或CPU利用這種比較，它只需花費1比較。但在進行漸近分析時，這並不重要。

---

1. https://en.wikipedia.org/wiki/Master_theorem
2. https://en.wikipedia.org/wiki/Asymptotic_analysis