STL二分查找函数的应用

应用二分查找的条件必须是数组有序！

其中二分查找函数有三个binary_serch,upper_bound,lower_bound

测试数组

int n1[]={1,2,2,3,3,4,5};

  int n2[]={5,4,3,3,2,2,1};

binary_serch

没有什么好说的，这个很简单，接受三个参数first,last,key三个值。如果在数组中查询到的话，那么就返回1否则返回0

代码

if(binary_search(n1,n1+7,3))

  cout<<1<<"\n";

  if(binary_search(n1,n1+7,8))

  cout<<2<<"\n";

输出的结果为1

upper_bound和lower_bound

upper_bound返回数组中第一个大于指定数的指针，lower_bound返回数组第一个小于等于指定数的指针，他们的基本用法都是first,last,key

解析图片

测试程序

cout<<n1[upper_bound(n1,n1+7,3)-n1]<<"\n";

  cout<<n1[lower_bound(n1,n1+7,3)-n1]<<"\n";

输出结果为4,3

解锁cmp参数

upper_bound和lower_bound都可以自定义排序用cmp函数

①默认a<b

bool cmp(int a,int b)

{

  return a<b;

}

这种情况及是最初的情况，并没有什么其他的变化

②降序数组a>b

bool cmp(int a,int b)

{

  return a>b;

}

这种情况是对于降序数列的的自定义，upper是小于的第一个位置的指针，lower是大于等于的第一个位置的指针

测试程序

cout<<n2[upper_bound(n2,n2+7,3,cmp)-n2]<<"\n";

  cout<<n2[lower_bound(n2,n2+7,3,cmp)-n2]<<"\n";

测试结果为2 3

如果加等号例如<-><=那么就是upper和lower的效果颠倒

完整测试程序

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a,int b)

{

  return a>b;

}

int main()

{

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

  int n1[]={1,2,2,3,3,4,5};

  int n2[]={5,4,3,3,2,2,1};

  if(binary_search(n1,n1+7,3))

  cout<<1<<"\n";

  if(binary_search(n1,n1+7,8))

  cout<<2<<"\n";

  cout<<n1[upper_bound(n1,n1+7,3)-n1]<<"\n";

  cout<<n1[lower_bound(n1,n1+7,3)-n1]<<"\n";

  cout<<n2[upper_bound(n2,n2+7,3,cmp)-n2]<<"\n";

  cout<<n2[lower_bound(n2,n2+7,3,cmp)-n2]<<"\n";

}