使用C 的lower_bound和upper_bound函數進行二分查找

lower_bound和upper_bound是C STL中的兩個常用函數，它們可以幫助我們在有序區間中進行二分查找。下面我們來看看它們的具體作用以及如何使用。 lower_bound函數的使用

lower_bound和upper_bound是C STL中的兩個常用函數，它們可以幫助我們在有序區間中進行二分查找。下面我們來看看它們的具體作用以及如何使用。

lower_bound函數的使用

lower_bound函數可以在一個有序區間中進行二分查找，并返回指向第一個大于等于給定值的元素位置的指針（或迭代器）。但是，在使用該函數之前，我們需要先對區間進行排序，通常會使用sort函數進行排序。

sort(首指針, 尾指針);
lower_bound(首指針, 尾指針, x);

需要注意的是，lower_bound函數接受的區間是左閉右開的，因此在使用時要注意區間的范圍。

lower_bound函數的迭代器版本

除了接受指針作為參數外，lower_bound函數還可以接受迭代器作為參數。例如，在使用STL vector時，我們可以直接使用begin()和end()函數來表示區間。

vectorlt;intgt; v;
sort((), v.end());
lower_bound((), v.end(), x);

使用迭代器作為參數，可以更加方便地操作STL容器。

upper_bound函數的使用

upper_bound函數和lower_bound函數的使用方法類似，它返回第一個大于給定值的元素的指針（或迭代器）。

sort(首指針, 尾指針);
upper_bound(首指針, 尾指針, x);

手寫lower_bound和upper_bound函數

雖然我們可以手寫lower_bound和upper_bound函數，但如果想要節省時間，直接調用STL函數會更加方便。不過，如果你對算法實現感興趣，也可以嘗試手動實現這兩個函數。

通過使用C 的lower_bound和upper_bound函數，我們可以快速在有序區間中進行二分查找，節省時間且提高效率。