swpuacm每周算法講堂-stl之二分_第1頁(yè)
swpuacm每周算法講堂-stl之二分_第2頁(yè)
免費(fèi)預(yù)覽已結(jié)束，剩余1頁(yè)可下載查看

下載本文檔

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

STL之二分Swpu-Nemaleswang

二分查找很簡(jiǎn)單，原理詳見(jiàn)Uestc-qsc的算法講堂。STL中關(guān)于二分查找的函數(shù)有三個(gè)lower_bound、upper_bound、binary_search。這三個(gè)函數(shù)都運(yùn)用于有序區(qū)間（當(dāng)然這也是運(yùn)用二分查找的前提）。其中如果尋找的value存在，那么lower_bound返回一個(gè)迭代器指向其中第一個(gè)這個(gè)元素。upper_bound返回一個(gè)迭代器指向其中最后一個(gè)這個(gè)元素的下一個(gè)位置（明確點(diǎn)說(shuō)就是返回在不破壞順序的情況下，可插入value的最后一個(gè)位置）。如果尋找的value不存在，那么lower_bound和upper_bound都返回“假設(shè)這樣的元素存在時(shí)應(yīng)該出現(xiàn)的位置”。要指出的是lower_bound和upper_bound在源碼中只是變換了if—else語(yǔ)句判定條件的順序，就產(chǎn)生了最終迭代器位置不同的效果。

binary_search試圖在已排序的[first,last)中尋找元素value，若存在就返回true，若不存在則返回false。返回單純的布爾值也許不能滿足需求，而lower_bound、upper_bound能提供額外的信息。事實(shí)上由源碼可知binary_search便是利用lower_bound求出元素應(yīng)該出現(xiàn)的位置，然后再比較該位置

的值與value的值。該函數(shù)有兩個(gè)版本一個(gè)是operator<，另外一個(gè)是利用仿函數(shù)comp進(jìn)行比較。ForwardIter

lower_bound(ForwardIterfirst,ForwardIterlast,const_Tp&val)算法返回一個(gè)非遞減序列[first,last)中的第一個(gè)大于等于值val的位置。ForwardIterupper_bound(ForwardIterfirst,ForwardIterlast,const_Tp&val)算法返回一個(gè)非遞減序列[first,last)中第一個(gè)大于val的位置1，lower_bound這個(gè)序列中可能會(huì)有很多重復(fù)的元素，也可能所有的元素都相同，為了充分考慮這種邊界條件，STL中的lower_bound算法總體上是才用了二分查找的方法，但是由于是查找序列中的第一個(gè)出現(xiàn)的值大

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論