【背景】

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

【源码运行环境】

操作系统:Windows 10

编译环境:Dev C++(基于C99标准)

【动态图解】

461877-20160721092729169-843824718.gif

461877-20160721092805029-903699213.gif

【源码】

递归实现:

/*
*方法名:binary_Search
*作用:折半查找,查找数组中是否存在指定元素,并返回位置
*参数:待查找数组 array; 起始位置 start ; 结束位置 end; 元素 element
*返回值:位置 position
*Author: WellLee
*最后一次修改时间:2018年12月6日 22:18:55 
*/
int binary_Search(int array[], int start, int end, int element)
{
	int mid;
	if(start > end)
	{
		return -999;
	}
	mid = (start + end) / 2;
	
	if(element == array[mid])
	{
		return mid;
	}
	else if(element >= array[mid])
	{
		return binary_Search(array,mid+1, end, element);
	}
	{
		return binary_Search(array,start, mid - 1, element);
	}
}

非递归实现:

/*
*方法名:Binary_Search
*作用:折半查找,查找数组中是否存在指定元素,并返回位置
*参数:待查找数组 array; 数组长度 length; 元素 element
*返回值:位置 position
*Author: WellLee
*最后一次修改时间:2018年12月6日 22:27:32
*/
int Binary_Search(int array[],int length, int element)
{
	int start = 0;
	int end   = length;
	int mid = 0;
	while(start <= end)
	{
		mid = (start + end) / 2;
		if(element == array[mid])
		{
			return mid;
		}else if(element > array[mid]){
			start = mid + 1;
		}else{
			end = mid - 1;
		}
	}
	return -999;
	
}

【分析】

折半查找的平均查找长度(ASL)计算公式如下:

假设表中每个记录的查找概率相等为:\( P_i = \frac{1}{n}\)

\(\begin{align} ASL &= \sum_{i=1}^{n} P_i C_i \\ &= \frac{1}{n} \sum_{i=1}^{h} j \cdot 2^{j-1} \\ &= \frac{n+1}{n} \log_2(n+1) -1 \end{align}\)

当n较大时,可近似看做:\(ASL = \log_2(n+1) -1\)

因此,折半查找的时间复杂度为\( O(\log_2 n)\)

【总结】

折半查找的优点是:比较次数少,查找效率高。

其缺点是:对表结构要求高,只能用于顺序存储的有序表。而有序表的构造需要付出较大的时间代价。

因此,折半查找不适用于数据元素经常变动的线性表。

【参考文献】

  • 《大话数据结构》.程杰.清华大学出版社

  • 《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社

作者 WellLee

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注