二分查找（c++）

二分查找（c++）

呵，提到查找一个数，肯定有很多人会说：“啊，暴力啊。”
说的不错，暴力是可以的

...
for (int i = 1; i <= n; i++) 
	if (a[i] == k) {
		cout << "YES" << endl;
		return 0;
	}
cout << "NO" << endl;
...

但是，很明显的缺点：费时O（n^2）
所以，我们需要一个更牛叉的办法：二分查找

int Find (int l, int r, int k) {
	int mid = l + r >> 1;
	if (a[mid] == k) return mid;
	if (a[mid < k] return Find (l + 1, r, k);
	if (a[mid] > k) return Find (l, r - 1, k);
}

当然，你也可以用系统自带的

lower_bound();
upper_bound();

例题 1.P2249 2.P1102 3.P1873 4.P1024 5.P1182

…