二進制搜索中止條件

每當我執行二進制搜索反覆，我總是在我是否應該使用while (low < high)或while(low <= high)混淆。二進制搜索中止條件

雖然這兩個工作，但有人可以告訴我什麼可能是一個比其他的實用優勢？

2016-02-07 Zanko

取決於你如何更新你的'low'和'high' – svs

您列出兩個終止條件取決於是否低和高的包括或不包括經常被使用。如果你的界限是包容性的，那麼當low = high時，數組中有一個元素需要檢查，而內部循環應該再運行一次。因此，測試低點是否合適高點是合適的。在另一方面，如果低是包容性和高是排他性的，那麼當低=高，你已用盡了所有的元素和完成，所以形式低<高是比較合適的考驗。

來源

2016-02-07 18:07:11 templatetypedef

謝謝。你認爲這可能是一個很好的實例嗎？假設每次我更新'high'如'中期 - 1'和'low'如'中間+ 1'，然後包容低和高獨家假定該元件是內部的陣列因此它是安全的終止，而無需檢查最後一個元素。但是，包含邊界安全地檢查最後一個元素，並用於不確定元素是否存在的情況？ – Zanko

我想這是有效的，但更常見的情況是在調用約定。你初始化爲數組的最後一個元素的索引（包含邊界）還是數組的長度（獨佔邊界）？ – templatetypedef

'lo = 0'和'hi = nums.length-1' – Zanko

二進制搜索中止條件

回答

相關問題