## 对分查找 binary search

这个查找的前提是建立在数组有序的基础上，我们可以通过对分的位置判断分区，从而快速找到目标节点
一般只能返回是否找到目标节点，而不能返回其位置，我们应该使用 标准迭代器
lower_bound(), upper_bound() 进行坐标确定，其中 lower_bouund 能从右侧逼近最靠近目标元素的位置； upper_bound 能从最左侧逼近最靠近目标元素的位置

什么样的集合是方便查找的？

从对分查找的经验里面我们可以知道，如果集合是有序的是很利于其查找的
但是很多时候我们会对一个集合进行操作，如何保持集合的有序性是一个很重要的问题
最直接的想法，是将两个数组用两个迭代器分别指向，然后比较将较小的值填充进新数组中。
但是，如果数组的同异集合性并不能通过数值来进行表示呢？
例如，在生物图谱中，我们如何知道人类和鱼类是否有相近的基因？假设生物学已经构建了以人为中心和以鱼类为中心的两个集合图，然后假设某一天有科学家证明了这两个集合图中的某对元素(a∈a\in 人, b∈b\in 鱼) 存在近亲关系，那么我们就可以将这两个集合合并到一起了，但是，我们还是想知道在这个集合中，东亚人和东亚鲤鱼是否存在亲属关系，相当于是在新的集合中查找是否同时存在同一个集合中，这并不是一个数值问题

并查集 union-find

假设在一个集合中，每个元素除了有自己的 index 之外还会保存做自己祖先的位置，初始状态下每个元素都没有祖先即其箭头指向其自身，那么我们在构建集合的时候，我们会在节点之间不断增加继承关系 (由于合并集合实际上是对称操作, 但是我们这里目的是找偏序关系"祖先", 因此我们需要绘制偏序箭头). 在完成继承的时候我们要将当前节点的祖先改成新的节点，同理如果新的节点本身的祖先不为其自身，当前节点会指向先前节点的祖先从而完成 路径压缩 (path comparison) , 这就很像 hessen diagram 中将某一个偏序关系进行不断链接到 root 的过程 (最高祖先的祖先箭头指向其自身)，区别在于，在并查集中，是不能存在多个祖先的

查找实现 find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find(int p){
	int root = p;
	// 找到根节点
	while ( root != parent[root]){
		root = parent[root];
	}
	// 路径压缩
	while (p != root) {
		int next = parent[p];
		parent[p] = root;
		p = next; 
	}
	return root;
}

在这个算法中，我们会首先找到根节点 root, 然后从当前节点 p 开始不断向上进行查找，并且将路过的节点的箭头都直接指向祖先节点 root

并集实现 union

1
2
3
4
5
6
7
8
9
10
11
12
void union(int p, int q){
	int rootP = find(p);
	int rootQ = find(q);
	if (rootP == rootQ) return;
	if (size[rootP] < size[rootQ]){  // 总是将小的节点合并到大的节点中
		parent[rootP] = rootQ;
		size[rootQ] += size[rootP];
	} else {
		parent[rootQ] = rootP;
		size[rootP] += size[rootQ];
	}
}