如何正確判斷二分邊界？
常見問題
- while 內條件是 \(\leq\) 還是 \(<\)
- left 和 right 的修改時用不用加 \(1\) 減 \(1\)
例題分析
例：
給定一個正整數 \(n( 1 \leq n \leq 1,000)\)，
第二行輸入 \(n\) 個整數 \(num_i(0 \leq num_i \leq 10,000)\)，保證嚴格單調遞增，第三行輸入一個整數 \(k( 0 \leq k \leq 10,000)\)，
若數列中有與 \(k\) 相等的數，輸出其下標，否則輸出 No，
一般來說，我們將二分分為左閉右閉，左閉右開兩種型別，
左閉右閉
首先我們根據上面容易出現的兩個問題進行分析，
- 因為當出現 left == right 是有意義的，所以 while 內使用 left <= right
- 如果 num[mid] > k 成立，則下標超過 mid 的數（包括 mid）都不正確，因此 right = mid - 1，
若是不成立，也不能判斷 num[mid] 是否等于 k，所以不能使 left = mid + 1，而是 left = mid，
不過在此題中可以直接判斷是否相等，相等直接輸出值即可，
左閉右開
還是根據上面兩個容易出錯的地方分析，
- 在左閉右開的區間里，left == right 沒有意義，所以 while 內使用 left < right
- 如果 num[mid] > k 成立，又由于區間是左閉右開的，所以可以直接使 right = mid，不成立時和上面左閉右閉的相同，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540284.html
標籤：其他
下一篇：Tarjan演算法求割點