轉載自:https://blog.csdn.net/qq_35620616/article/details/70232489?

1.lower_bound的第四個參數的用法：

先看代碼：

#include <bits/stdc++.h>
using namespace std;
struct node{
? ? int x,y;
};
struct cmp{
? ? int operator()(const node a,const node b){
? ? ? ? return a.x<b.x;
? ? }
};
int main(){
? ? node num[1000];
? ? for(int i=0;i<=100;i++){
? ? ? ? num[i].x=i;
? ? ? ? num[i].y=100-i;
? ? ? ? printf("%d ",num[i].x);
? ? }
? ? printf("\n");
? ? while(1){
? ? ? ? node t;
? ? ? ? scanf("%d",&t.x);
? ? ? ? printf("%d\n",num[(lower_bound(num,num+100,t,cmp())-num)].x);
?
? ? }
}
大致的模板就是這樣，注意，引用cmp的時候是有()的。

下面來解釋一下加入cmp()參數的lower_bound的運行過程

struct cmp{
? ? int operator()(const node a,const node b){
? ? ? ? return a.x<b.x;
? ? }
};
在這里，a代表的就是num數組的數字，而b代表的就是要比較的數字，如果cmp的retur是1的話那么二分查找就會往右邊進行，而如果是0的話那么就會往左邊進行。
我們還是舉數據來解釋吧

假設mid代表num區間的中間位置

比方說輸入的是個68，那么首先68會和50(二分查找嘛，自然是從num數組的中間開始進行比較的拉)進行比較因為50<68為1，那么mid就會往右跑了，接下來因為75<68為零所以mid又會往左跑，接下來就是63<68然后mid又往右跑，直到逼近到<=68的數字中最接近68的數字

假設cmp是這樣的就比較神奇了：

struct cmp{
? ? int operator()(const node a,const node b){
? ? ? ? return a.x>b.x;
? ? }
};
這次拿68和49舉例
對于68而言50>68不滿足，然后往左跑，然后越跑越不滿足，于是就輸出了0；

對于49而言50>49滿足，然后往右跑，越跑越滿足根本停不下來直到跑到最右端于是就輸出了100......

注意：如果這是一個遞減的序列的話那么cmp也要發生變化，具體怎么變參照上面的例子，（主要是因為太長不想寫.......哈哈哈.......）

對于upper_bound就比較神奇了，它是這么利用cmp的：

struct cmp{
? ? int operator()(const node a,const node b){
? ? ? ? return a.x<b.x;
? ? }
};

a代表要比較的數字，b代表num數組，如果return為1就往左跑，否則往右跑。（我會告訴你之所以我這么認為僅僅是因為這符合我的經驗法則嗎）
我們還是舉例吧，比如num序列是這樣的：

11223344

12345678（這一行代表上面那些數字對應的下標）

當用lower_bound來查找2應該插入哪個位置的時候是這樣的:首先num[4]與2比較,num[4]<2是false的，所以往左跑；然后num[2]<2是true的，往右跑；直到逼近到num[3]這個位置

當用upper_bound來查找2應該插入哪個位置的時候是這樣的:首先2與num[4]比較。2<num[4]是false的，所以往右跑，然后2<num[6]是true的，往左跑，直到逼近到num[5]這個位置；

具體的cmp形參的變化過程看官可以用以下代碼測試以下：

#include <bits/stdc++.h>
using namespace std;
struct node{
? ? int x,y;
};
struct cmp{
? ? int operator()(const node a,const node b){
? ? ? ? printf("*%d %d\n",a.x,b.x);
? ? ? ? return a.x<b.x;
? ? }
};
int main(){
? ? node num[1000];
? ? for(int i=0;i<=100;i++){
? ? ? ? num[i].x=i/10;
? ? ? ? num[i].y=100-i;
? ? ? ? printf("%d ",num[i].x);
? ? }
? ? printf("\n");
? ? while(1){
? ? ? ? node t;
? ? ? ? scanf("%d",&t.x);
? ? ? ? printf("%d\n",num[(lower_bound(num,num+100,t,cmp())-num)].x);
? ? ? ? printf("%d\n\n",num[(upper_bound(num,num+100,t,cmp())-num)].x);
?
? ? }
}

另外，set和map，和map容器也有直接的內置二分查找，這樣使用：

set<int>s;

s.upper_bound()或者s.lower_bound(這里填參數);

注意:

對于map<first_int,second_int>，他的lower_bound實在first_int里面查找你填入的參數的：比如這樣

#include <bits/stdc++.h>
#define LL long long
#define inf 1e9+1
using namespace std;
int main(){
? ? map<int ,int>m;
? ? for(int i=1;i<=5;i+=2)m[i]=i+4;
? ? printf("%d\n",*m.lower_bound(2));
}

特別聲明！特別聲明！
本人不保證上面內容確實是lower_bound和upper_bound真正的實現方法，只是在本人的一些測試中上面的這些能夠正常解釋我的所有樣例。
如果有路過dalao發現任何錯誤還望提出，以免誤人子弟。謝謝！
?

總結

以上是生活随笔為你收集整理的lower_bound,upper_bound的第四个参数的用法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。