学步园

查找算法中的“二分法”是这样定义的：

    给定N个从小到大排好序的整数序列List[]，以及某待查找整数X，我们的目标是找到X在List中的下标。即若有List[i]=X，则返回i；否则返回-1表示没有找到。

    二分法是先找到序列的中点List[M]，与X进行比较，若相等则返回中点下标；否则，若List[M]>X，则在左边的子系列中查找X；若List[M]<X，则在右边的子系列中查找X。

    试写出算法的伪码描述，并分析最坏、最好情况下的时间、空间复杂度。

int search(int List[],int x);
{
	int f=-1;
	min=0;
	max=strlen(List);
	n=(max+min)/2;
	while(min<max)
	{
		if(List[n]>x)
		max=n;
		else
		min=n;
		n=(max+min)/2;
		if(List[n]==x)
		f=n;
	}
	return f;
}

空间复杂度：S(n)=n;  n个数需要存n个所以空间复杂度为n。
时间复杂度：
最坏时间复杂度为找不到List[n]==x的情况：T(n)=O(log2(n));
最好时间复杂度：一次就找到。T(n)=O(1);