編程珠璣：列9.3二進制搜索 - 範圍初始化

Question

在9.3節工作賓利將修改過的二進制搜索。在9.3

if (arr[mid] < key) low = mid+1 
else if (arr[mid] > key) high = mid-1 
else return mid; 

顯示

典型實施的簡要剪斷和更好的方法用不同的不變量改性/有效的比較..

if (arr[mid] < key) low = m; 
else high = m; 

和環形外還有一個檢查，如果索引中的密鑰「高」。在修改的二進制搜索左索引「低」開始於-1（而不是0）和「高」指數以n（而不是n-1）開始..和循環運行

while (low + 1 != high) 

該修改即使設置low = 0和high = n-1，搜索似乎也能正常工作。

但我寧願不要在他的代碼中猜想賓特賓利。那麼，爲什麼他設置爲-1和高到n？有沒有什麼特殊情況只有這樣才能起作用？

Answer 1

如果你有一個數組是空的（n == 0），然後while(low + 1 != high檢查）才能正常終止，如果low始於-1和high在0。

while((-1 + 1) != 0) //true

如果low開始在0代替，或high開始在-1（或兩者），則該循環將清楚地執行至少一個檢查：

• while((0 + 1) != 0) // false
• while((-1 + 1) != -1) // false
• while((0 + 1) != -1) // false

對空數組的檢查可能會訪問超出邊界的索引，該索引會調用未定義的行爲。