二分基础

二分

(类似于单调函数求零点)

二分查找

• 在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在哪个部分中并调整集合上下界，重复直到找到目标元素
  题目:
  给定一串n个单调递增的数，有q次询问>=x且<=y的数有多少个
  数据规模:1$ \leq n \leq10^5$ 1$\leq q \leq 50000 $

手动实现
写法一
(注意下取整，避免死循环)

//找>=x的第一个位置 
while(l < r){
	mid = (l + r) / 2;
	if(a[mid] >= x) r = mid;
	else l = mid + 1;
}

//答案是r

//找<=x的第一个位置 
while (l < r) {
	mid = (l + r + 1) / 2;	//因为是下取整，所以要+1，避免出现l=l的情况 eg:3 3 3出现死循环
	if(a[mid] <= x) l = mid;
	else r = mid - 1;
}

写法二
(永远把\(mid\)丢掉，但是要用\(ans=min(ans, mid)\)记录答案)；

//找>=x的第一个位置
while (l <= r) {
	mid = (l + r) / 2;
	if(a[mid] >= x) r = mid - 1;	//ans是最后一次a[mid]>=x成立的mid，所以ans=r+1也就是l
	else l = mid + 1;
}

//答案就是 r+1 或者 l

//找<=x的第一个位置
while (l <= r) {
	mid = (l + r) / 2;
	if(a[mid] <= x) l = mid + 1;	//ans是最后一次a[mid]<=x成立的mid，所以ans=l-1
	else r = mid - 1;
}

Ending Edition

//找>=x的第一个位置
while(l <= r) {
	mid = (l + r) / 2;
	if(a[mid] >= x){
		r = mid - 1;
		ans = min(ans, mid);
	}else{
		l = mid + 1;
	}
}

//找<=x的第一个位置
while(l <= r) {
	mid = (l + r) / 2;
	if(a[mid] <= x){
		l = mid + 1;
		ans = min(ans, mid);
	}else{
		r = mid - 1;
	}
}

C++STL的二分查找函数

• binary_search 返回bool值，是否存在
• lower_bound 从已排好序的序列a中利用二分搜索找出指向满足\(a_i \geq k\)的\(a_i\)的最小的指针
• upper_bound 从已排好序的序列a中利用二分搜索找出指向满足\(a_i > k\)的\(a_i\)的最小的指针
  如果想要知道下标，减去a即可
  Eg:lower_bound(a, a + 11, 55);