二分的一些收获

二分的一些收获

• 二分搜索函数：

#include<iostream>
using namespace std;
#include<algorithm>
int rfind(int a[],int mm,int num)
{int l=0,r=num-1;while(l<=r){int m=l+(r-l)/2;if(a[m]==mm)return m;else if(a[m]>mm){r=m-1;}elsel=m+1;}return -1;
}
int main()
{int num;cin>>num;int a[num];for(int i=0;i<num;++i)cin>>a[i];sort(a,a+num);int rsearch;cin>>rsearch;cout<<rfind(a,rsearch,num);
}

• 心得：我们在if else的时候选择了左边更新为中间值+1，右边为相应的中间值-1，是为了能够跳出while循环。

• 写一个函数LowerBound，在包含size个元素的、从小到大排序的int数组a里查找比给定整数p小的，下标最大的元素。找到则返回其下标，找不到则返回-1

#include<iostream>
using namespace std;
#include<algorithm>
int rfind(int a[],int mm,int num)
{int l=0,r=num-1;int las=-1;while(l<=r){int m=l+(r-l)/2;if(a[m]>=mm){r=m-1;}else if(a[m]<mm){l=m+1;las=m;}}return las;
}
int main()
{int num;cin>>num;int a[num];for(int i=0;i<num;++i)cin>>a[i];sort(a,a+num);int rsearch;cin>>rsearch;cout<<rfind(a,rsearch,num);
}

• 心得：（1）如果中间的数>=搜索的数那么更新r；否则更新l和las；