二分查找

当我们要在数组中搜索一个数据，常常会享受到极大的复杂度，如硬搜O（n）,二叉搜索树O（n）（期望）等。
所以，今天我们来引入一个新的对单调数列进行搜索的方法——二分搜索。
如下数列：
1 3 7 8 12 15 17 22
我们在数列中查找17这个数
如果直接遍历，就会享受到O（n）的复杂度
但是如果我们使用二分查找
先查8,17>8；
再查15,17>15;
再查17,17==17，返回17的地址（下标）7
易知此时时间复杂度为O（log n），远小于遍历的O（n）
那么，代码长的是这个样子的

int a[10001];
int find(int l, int r, int x)
{
	while(l <= r)
	{
		int mid = (l + r)/2;
		
		if(a[mid] >= x)
		{
			r = mid - 1;
		}else
		{
			l = mid + 1;
		}
	}	
	return r;
}

众所周知，OI比的就是搜索
好了就是这样