Algorithms-二分

二分法太常用了，学了又忘，忘了再来吧。

整数集合上二分

二分难在版本太多了，用起来总是让人头晕，比如：
Binary_search1:

又如：

int Binary_search2(int l,int r)
{
	while(l <= r)
	{
		int mid=(l+r)/2;
		if(a[mid]>=x) r=mid-1;
		else  l=mid+1;
	}
	return mid;
}

还有：

int Binary_search3(int l,int r)
{
	while(l < r)
	{
		int mid=(l+r)/2;
		if(a[mid]>x) l=mid+1;
		else if(a[mid] < x)r=mid-1;
		else break;
	}
	return mid;
}

为什么会出现这么多版本方法？
究其原因，是因为：
首先，二分法是一种不断逼近的算法，不断在实数域上逼近一个答案，然而，由于计算机的整除是下取整的，这就会导致这个算法在实现上并不会尽如人意。所有的版本都是在避免一种情况：死循环。

三个版本都是对同一种情况的不同解决办法，下面逐一考虑：

考虑Binary_search1:

这个代码不对称？求大于等于和求小于等于写法不同？为什么？
感觉这个版本是最难的，但是，理解这个代码为什么会这样写，是对彻底理解二分死循环帮助最大的。

自然地，二分，mid=(l+r)/2，要取正中间才对（理论上），可是实际上是这样吗？
考虑这种情况：

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

l = r - 1
mid = (l + r) / 2
mid = l(下取整)
a[mid] <= x
l = mid = l
mid = (l + r) / 2
a[mid] <= x
l = mid
…………死循环

那怎么改呢，让mid=(l+r+1)/2，变成了上取整，于是就有了Binary_search1

那怎么改呢，让循环条件l<=r，l=mid-1，让两个指针错过后取中间，于是就有了Binary_search2

那怎么改呢，让循环条件不变，单独考虑a[mid]=x时，再加一个else分支判断一下，于是就有了Binary_search3

没明白？

可是现在还是没明白为什么b1要分情况两种写法，而b2,b3只需一种写法即可。
打个比方，三个方法都在设计夹子夹住答案，而b1就是设计了一把不对称的夹子，或左大右小（下取整），或左小右大（上取整）
另外两种夹子写起来是对称的，所以省心些。

还是没明白？

可是现在还没明白为什么一会上取整，一会又下取整？
其实二分法本身就不对称，答案是一个整数，要么从左边趋近它，要么从右边趋近它，这就要考虑不同情况。

就是想用basesearch1？

《算法竞赛-进阶指南》给出了指导意见：

例题：线性表整数二分查找

▶

title:code

#include<bits/stdc++.h>
using namespace std;

#define MAXSIZE 10
#define NotFound 0

typedef int ElementType;
typedef int Position ;
typedef struct LNode *List;

struct LNode
{
	ElementType Data[MAXSIZE];
	Position Last;
};

List CreatList();
Position BinarySearch(List ,ElementType X);

List CreatList()
{
	List L;
	L = (List)malloc(sizeof(struct LNode));
	L->Last = -1;
	return L;
}
Position BinarySearch(List L,ElementType X)
{
	int left = 1;
	int right = L->Last;
	while(left < right)
	{
		int center = (left+right) / 2;
		if(X > L->Data[center])
		{
			left = center + 1;
		}else if(X < L->Data[center])
		{
			right  = center - 1;
		}else{
			return center;
		}
	}
	return NotFound;
}
int main()
{
	List L;
	ElementType X;
	Position P;
	
	L = CreatList();
	for(int i = 1;i < 4;++ i)
	{
		L->Data[i] = 2 * i - 1;
	}
	L->Last = 3;
	scanf("%d",&X);
	P = BinarySearch(L,X);
	printf("%d\n",P);
	
	return 0;
}