lower_bound和upper_bound是C STL中的兩個(gè)常用函數(shù)，它們可以幫助我們?cè)谟行騾^(qū)間中進(jìn)行二分查找。下面我們來(lái)看看它們的具體作用以及如何使用。 lower_bound函數(shù)的使用

lower_bound和upper_bound是C STL中的兩個(gè)常用函數(shù)，它們可以幫助我們?cè)谟行騾^(qū)間中進(jìn)行二分查找。下面我們來(lái)看看它們的具體作用以及如何使用。

lower_bound函數(shù)的使用

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

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

需要注意的是，lower_bound函數(shù)接受的區(qū)間是左閉右開(kāi)的，因此在使用時(shí)要注意區(qū)間的范圍。

lower_bound函數(shù)的迭代器版本

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

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

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

upper_bound函數(shù)的使用

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

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

手寫(xiě)lower_bound和upper_bound函數(shù)

雖然我們可以手寫(xiě)lower_bound和upper_bound函數(shù)，但如果想要節(jié)省時(shí)間，直接調(diào)用STL函數(shù)會(huì)更加方便。不過(guò)，如果你對(duì)算法實(shí)現(xiàn)感興趣，也可以嘗試手動(dòng)實(shí)現(xiàn)這兩個(gè)函數(shù)。

通過(guò)使用C 的lower_bound和upper_bound函數(shù)，我們可以快速在有序區(qū)間中進(jìn)行二分查找，節(jié)省時(shí)間且提高效率。