c++二分查找?guī)旌瘮?shù)

c++二分查找?guī)旌瘮?shù)二分查找是一種基于比較的查找算法，它的基本思想是將查詢的關(guān)鍵字與表中間位置的關(guān)鍵字進(jìn)行比較，根據(jù)比較結(jié)果來確定待查關(guān)鍵字在前半部分還是后半部分中進(jìn)行查找，從而在每一個比較的過程中把待查范圍縮小一半。二分查找雖然算法簡單，但是實(shí)現(xiàn)過程還是比較繁瑣的，因此常常使用庫函數(shù)來進(jìn)行快速實(shí)現(xiàn)。

C++標(biāo)準(zhǔn)庫提供了對于二分查找的支持，在<algorithm>頭文件中提供了以下兩個函數(shù)：

1.binary_search

binary_search是C++STL中二分查找的核心函數(shù)，它的原型如下：

template<classForwardIt,classT>

boolbinary_search(ForwardItfirst,ForwardItlast,constT&value);

binary_search函數(shù)的輸入是迭代器first和last、要查找的值value，函數(shù)返回值為bool類型，表示是否找到待查找的值。需要注意的是，輸入的區(qū)間[first,last)必須按照升序排序，如果不滿足條件，則結(jié)果是undefinedbehavior。

binary_search的實(shí)現(xiàn)原理是不斷地將區(qū)間[first,last)劃分成兩個子區(qū)間，從而逐漸縮小查找范圍，最終找到待查找值，或者將區(qū)間縮小至只有一個元素時退出循環(huán)。

2.lower_bound

lower_bound函數(shù)用于在一個已經(jīng)排好序的序列中查找第一個不小于目標(biāo)值的元素位置，其原型如下：

template<classForwardIt,classT>

ForwardItlower_bound(ForwardItfirst,ForwardItlast,constT&value);

lower_bound函數(shù)的輸入和binary_search類似：迭代器first和last表示待查找元素的范圍、value表示待查找的值。不同的是，lower_bound不僅返回查找結(jié)果是否成功的bool值，還返回查找到的元素的迭代器。

lower_bound的實(shí)現(xiàn)原理和binary_search相似，區(qū)別在于lower_bound首先找到第一個大于等于目標(biāo)值的元素位置，而不是判斷目標(biāo)值是否在序列中。

需要注意的是，binary_search和lower_bound均只適用于有序序列，如果序列無序，則可能返回錯誤結(jié)果。同時，這兩個函數(shù)也是二分查找算法中的特例，可以用更一般的二分查找算法來實(shí)現(xiàn)，以適用于更為廣泛的應(yīng)用場景。

總之，二分查找是一種非常實(shí)用的算法，常常應(yīng)用于搜索大規(guī)模數(shù)據(jù)的場景中，例如查找有序數(shù)組中的元素、查找字符串中的某一個字符等等。C++的標(biāo)準(zhǔn)庫中提供了bina