查找算法之二分法

时间:2021-11-30 00:48:21

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

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

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

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

查找算法之二分法

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

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