二分查找
二分查找
简介
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
——百度百科
有序排列
sort (a + 1, a + n + 1, cmp);时间复杂度 O(logn)
学了二分以后给我的感觉就是很多东西都可以拿来二分，以前以为只有查找可以用二分，现在知道原来很多有范围的东西，都可以用二分来逼近答案。
整数二分
找 >= s 的数中最小的
记录答案
bool check (int x) { if (a[x] >= s) return 1; else return 0; } int l = 1, r = n, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (check (mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } printf ("%d", a[ans]);不记录答案 · r 逼近答案
int l = 1, r = n; while (l < r) { int mid = (l + r) / 2; if (a[mid] >= s) r = mid; else l = mid + 1; } printf ("%d", a[r]);如果 a[mid] >= s 成立，接下来应该向左继续查找，而此时 mid 是符合要求的，所以要保留，因此 r = mid
- 如果 a[mid] >= s 不成立，接下来应该向右继续查找，而此时 mid 是不符合要求的，所以要舍弃，因此 l = mid + 1
- 输出的数一定是要符合要求的，每次查找 r = mid，r一定是符合要求，而 l 不一定，所以输出 r
找 < s 的数中最大的
记录答案
bool check (int x) { if (a[x] < s) return 1; else return 0; } int l = 1, r = n, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (check (mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } printf ("%d", a[ans]);不记录答案 · l 逼近答案
int l = 1, r = n; while (l < r) { int mid = (l + r + 1) / 2; if (a[i] < s) l = mid; else r = mid - 1; } printf ("%d", a[l]);如果 a[mid] < s 成立，接下来应该向右继续查找，而此时 mid 是符合答案的，所以要保留，因此 l = mid
如果 a[mid] < s 不成立，接下来应该向左继续查找，而此时 mid 是不符合答案的，所以要舍弃，因此 r = mid - 1
输出的数一定是要符合要求的，每次查找 l = mid，l一定是符合要求，而 r 不一定，所以输出 l
浮点二分
浮点二分只能用记录答案方法，而且要设置一个范围使得查找能退出循环
const double eps = 1e-8;
double l = 0, r = n;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check (mid))
{
ans = mid;
r = mid;
}
else l = r;
}
printf ("%d", ans);