查找算法之二分法

写这个的原因是因为写二分算法的时候脸被打的好疼，痛定思痛之后决定详细写一下关于二分查找算法！

使用二分查找，必须满足一个很重要的点：数组是排序好的

二分查找实际上就是一个递归查找左右子树的过程

查找本身的过程就是一颗树，所以有二分查找树之说，这个树的每个根节点，都满足：左子树的值<=根节点值<=右子树值

一个二分查找而言，通常需要三个标志量

low middle high

front和last好说，是当前查找区间的上下限，重点是这个middle 

①首先，尽可能让元素取闭区间 [low, high]，开区间也行，但是闭区间肯定是没有问题的

②其次middle = low + (high - low)/2，不直接使用（high+low)/2 是为了防止溢出

③终结条件是low > high，此时表明搜索空间为空了，不要用low != high之类的，如果是在查找一个不在该数组中的元素，这时low != high相当于死循环

说到底：二分查找就是不断缩小搜索空间的过程

代码：

int binarySearch(vector<int> &nums, int target)
{
	int low, high, mid;
	low = 0;
	high = nums.size() - 1;				//注意采用[0, length - 1]的闭区间
	while (low <= high)
	{
		mid = low + (high - low) / 2;				//防止溢出
		if (target < nums[mid]) high = mid - 1;
		else if (target > nums[mid]) low = mid + 1;
		else return mid;
	}

	return -1;
}

PS：之前还自我感觉良好，看来基本功还是不行，还是too young, too simple, sometimes naive!!!  QAQ