Posted on 

C++ 二分查找算法

用法一

1
binary_search(数组名+n1, 数组名+n2, 值)

含义:
查找在[n1,n2)范围内等于“值”的元素。返回truefalse

用法二

1
binary_search(数组名+n1, 数组名+n2, 值, 排序规则结构名());

查找时的排序规则必须和排序时的规则一致。

示例:binary_search.cpp · GitHub

lower_bound(查找下界)

1
T * lower_bound(数组名+n1, 数组名+n2, 值);

返回指针 T * p
*p是查找区间里下标最小的,大于等于“值”的元素
如果找不到,*p指向下标为n2的元素。

1
T * lower_bound(数组名+n1, 数组名+n2, 值, 排序规则结构名());

*p是查找区间里下标最小的,按照自定义排序规则, 可以排在值后面的元素。
如果找不到,*p指向下标为n2的元素。

upper_bound(查找上界)

1
T * upper_bound(数组名+n1, 数组名+n2, 值);

返回指针 T * p
*p是查找区间里下标最小的,大于“值”的元素
如果找不到,*p指向下标为n2的元素。

1
T * upper_bound(数组名+n1, 数组名+n2, 值, 排序规则结构名());

*p是查找区间里下标最小的,按照自定义排序规则, 必须排在值后面的元素。
如果找不到,*p指向下标为n2的元素。

示例: lower_upper_bound.cpp · GitHub

平衡二叉树

有时需要在大量增加、删除数据的同时,还要进行大量数据的查找。
排序+二分查找显然不可以,因加入新数据就要重新排序。
可以使用“平衡二叉树”数据结构存放数据,体现在STL中,是以下四种“排序容器”:

  1. Multiset
  2. Set
  3. Multimap
  4. Map

multiset

1
multiset<T> st;

作用:

  1. 定义一个multiset变量st,里面存放T类型的数据,并且能自动排序。开始st为空。
  2. 排序规则: 表达式 a<btrue 则a排在b前面。
  3. 元素操作:
    1. st.insert 添加元素
    2. st.find查找元素
    3. st.erase删除元素

示例: multiset.cpp · GitHub

set

setmultiset都区别: 容器内不能有重复元素。
因此不存在“a和b重复“。

set插入元素可能不成功。

示例: set.cpp · GitHub

pair模版

pair<T1, T2>类型等价于:

1
2
3
4
struct {
T1 first;
T2 second;
};

例如:pair<int,double> a等价于:

1
2
3
4
struct {
int first;
double second;
} a;

可以对其进行操作:

1
2
a.first = 1;
a.second = 93.93;

pair可以被用来验证set插入元素是否成功。
以下是set一个完整的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// set
#include <iostream>
#include <cstring>
#include <set> // 使用multiset和set
using namespace std;

int main()
{
set<int> st;
int a[10] = {1,3,9,2,87,12,91,55,90,90}; // 包含重复元素90
for (int i=0; i<10; ++i)
{
st.insert(a[i]);
}
cout << st.size() << endl; // size=9
set<int>::iterator i;
for(i=st.begin(); i!=st.end(); ++i)
{
cout << *i << ","; // 逐项输出
}
cout << endl;
pair<set<int>::iterator, bool> result = st.insert(3);
if (!result.second)
cout << *result.first << "already exists!" << endl;
else
cout << *result.first << "inserted." << endl;
return 0;
}
开往-友链接力
A member of 开往-友链接力

This site was deployed by @OasisLee using Stellar.

本站由Vercel提供托管与Serverless支持 | PlanetScale提供数据库支持