二分查找

二分查找（binary search），也称折半搜索（half-interval search）

二分查找的对象必须是排列好的数组。

二分查找的最优时间复杂度为 $O(1)$，最坏时间复杂度为 $O(logn)$。

在二分查找中，每次迭代都会将查询区间减半，因而对于所有的n来说，时间复杂度是$O(logn)$。

二分查找算法的迭代实现：

int binary_search(int start, int end, int key) {
	int ret = -1; // 未搜索到数据返回-1下标
	int mid;
	while (start <= end){
		mid = start + ((end - start) >> 1); // 直接平均可能会溢出，所以用这个算法
		if (arr[mid] < key)
			start = mid + 1;
		else if (arr[mid] > key)
			end = mid - 1;
		else { // 最后检测相等是因为多数搜索情况不是大于就是小于
			ret = mid; 
			break;
		}
	} return ret; // 单一出口
}