二分法精讲剖析及个人理解（通俗，适合新手）-《算法笔记》同步笔记总结与补充

2020-03-02

二分法这一章，做题时的难度明显感觉要高于前几章

专题要点：

对二分思想的掌握与运用是这一专题的要点，个人认为，理解二分思想中的二分取值（即left,right,mid），二分判断条件（mid > key, mid < key, mid == key），二分的循环条件（left < right, left <= right），二分的返回值（return left/right, return mid）尤为重要！！！可以自己先问一下自己，这几点是否完全明白，而非模棱两可。

二分思想：

1、二分前提：二分法运用的前提条件即为有序性，因此在做题时，如果有明显的有序性，可以考虑二分法，若无明显的有序性，考虑能否将数据转化为有序的（排序或进行一些运算，比如计算自序和的运算）
2、二分取值：left，right作为区间的两个端点，根据二分判断条件进行左右移动；mid作为中点主要是用来标出要查找数据的位置，并进行二分判断的
3、二分判断条件，二分循环条件与二分返回值可以根据查找目的不同，分为两种查找方式：
①查找满足相等关系的元素是否存在
二分判断条件：由于查询元素是否存在，含义是存在返回下标，不存在则需要指明查询失败，因此需要对mid和key的大于关系，小于关系，等于关系分别处理
二分循环条件：left <= right，出现left>right的情况跳出循环，这种情况发生于当left,mid,right指向同一个数时，这个数还不是目标值，则left>right，则整个查找结束返回-1
二分返回值：若元素存在，则mid==key条件成立，返回mid，若元素不存在，出现left > right，跳出循环，返回-1

int binarySearch(int left, int right, int key)
{
	while(left <= right)
	{
		mid = (left + right) / 2;
		if(mid == key)
		{
			return mid;
		}
		else if(mid < key)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	return - 1;
}

②查找满足不等关系的元素：
代表upper_bound(), lower_bound()函数，以lower_bound()为例
二分判断条件：由于要查找的目标不一定会存在，而我们的目的也并不是要知道其是否存在，因此只有两个判断条件（少了单独判断mid == key），而mid>=key或mid<key最好需要画图推导！
二分循环条件：left<right，最终当出现left==right时，循环结束，此时left=right=mid，若该元素存在，则返回这个元素的位置；若该元素不存在，则返回可以插入该元素（大于key值）的位置（或者说是它应该在的位置）
二分返回值：由于在left=right时循环结束，因此此时return left与return right含义一样
4、二分法可解的问题类型：寻找位置与寻找值
①寻找有序序列中第一个满足某条件的元素位置（同样，最后一个满足条件的元素位置也可以完成）
②数据在某一区间上取值，寻找满足条件的数据值

//返回第一个大于等于x的元素位置
int lowerBound(int a[], int left, int right, int x)
{
	int mid;
	while(left < right)
	{
		mid = (left + right) / 2;
		if(a[mid] >= x)
		{
			right = mid;
		} 
		else if(a[mid] < x)
		{
			left = mid + 1;
		}
	}
	return left;
	//return right;//均可 
}
//返回第一个大于x的元素位置
int upperBound(int a[], int left, int right, int x)
{
	int mid;
	while(left < right)
	{
		mid = (left + right) / 2;
		if(a[mid] > x)
		{
			right = mid;
		}
		else if(a[mid] <= x)
		{
			left = mid + 1;
		}
	} 
	return left;
}