二分的理解

今天在写一道二分的题的时候，使用二分后得到的结果并不是想要的。于是怀疑起自己是否打错板子了，后面发现并没有，但也让我明白了哪里不足。

二分有两种通用的板子

第一种

	int l = 0, r = n, mid;
	while(l < r)
	{
		mid = (l + r) >> 1;
		if(a[mid] >= x) r = mid;
		else l = mid + 1;
	}

第二种

	l = 0, r = n, mid;
	while(l < r)
	{
		mid = (l + r + 1) >> 1;
		if(a[mid] <= x) l = mid;
		else r = mid - 1;
	}

其中第一种通常用来找比x大的第一个数，第二个用来找比x小的最后一个数

例如：x = 3
a[] = {1，2，4，4，5}；
此时第一种会找到4， 第二种会找到2

但这有个前提条件就是数组中没出现过x， 如果出现，那么第一种将找到第一个等于x的位置，第二种将找到最后一个等于x的位置

例如：x = 3
a[] = {1,2,3,3,3,4};
此时第一种会找到下标为2，数值为3的元素，第二种会找到下标为4，数值为3的元素