? lower_bound算法返回第一個大于等于給定值所在的位置。設(shè)置兩個指針start和last，其中start指向數(shù)組的起始位置，last指向數(shù)組末尾位置之后的位置。當(dāng)start和last指向相同位置時循環(huán)結(jié)束。mid指向[start,last)區(qū)間的中間位置，當(dāng)中間位置元素值大于等于給定val時，說明第一個大于等于val值在mid位置的左邊，更新last為mid。當(dāng)中間位置元素值小于給定的val時，說明第一個大于等于val值在mid右邊，不包括mid所在的位置。更新start為mid+1。
?

int myLowerBound(vector<int> &data, int k) {int start = 0;int last = data.size();while (start < last){int mid = (start + last) / 2;if (k > data[mid]) start = mid + 1;else last = mid;}return start; }

? ? upper_bound算法返回第一個大于給定元素值所在的位置，設(shè)置兩個指針start和last，其中start指向數(shù)組的起始位置，last指向數(shù)組末尾位置之后的位置，當(dāng)start和last指向相同位置時循環(huán)結(jié)束，mid指向[start,last)區(qū)間的中間位置，當(dāng)中間位置元素值小于等于給定val時，說明第一個大于val值在mid位置的右邊更新start為mid+1。當(dāng)中間位置元素值大于給定元素時，說明第一大于在mid左邊，包括mid所在位置，所以更新last為mid。

int myUpperBound(vector<int> &data, int k) {int start = 0;int last = data.size();while (start < last){int mid = (start + last) / 2;if (k >= data[mid]) start = mid + 1;else last = mid;}return start; }

---

以上都是，左端是滿足值。特點就是都是l永遠(yuǎn)都是=mid+1，r永遠(yuǎn)都是=mid

下面再來一發(fā)，右端是滿足值的（至于是lower還是upper，就看ok函數(shù)中加不加等號就可以了）：（找一個特例，比如只有兩個值的模擬一下）

while(l<r) {m=(l+r+1)/2;if(ok()) l=m;else r=m-1;}printf("l = %d\n",l);

?等價于：（左端滿足值的就是在else中ans=m就可以了，比較好實現(xiàn)）

while(l<=r) {m=(l+r)/2;if(ok()) l=m+1,ans=m;else r=m-1;}printf("ans = %d\n",ans);

關(guān)于binarysearch ??https://blog.csdn.net/daniel_ustc/article/details/17307937

upper_bound再來一種實現(xiàn)：

int Search(int num,int low,int high) {int mid;while(low<=high){mid=(low+high)/2;if(num>=b[mid]) low=mid+1;else high=mid-1;} return low; }

紀(jì)念編輯時間：2018.10.08? 10:12:42

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的给不会调用C++STL库中二分函数lower_bound,upper_bound,binary_search同学的一些话！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。