【背景】
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
【源码运行环境】
操作系统:Windows 10
编译环境:Dev C++(基于C99标准)
【动态图解】
【源码】
递归实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | /* *方法名: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); } } |
非递归实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | /* *方法名: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)计算公式如下:
假设表中每个记录的查找概率相等为:
当n较大时,可近似看做:
因此,折半查找的时间复杂度为
【总结】
折半查找的优点是:比较次数少,查找效率高。
其缺点是:对表结构要求高,只能用于顺序存储的有序表。而有序表的构造需要付出较大的时间代价。
因此,折半查找不适用于数据元素经常变动的线性表。
【参考文献】
-
《大话数据结构》.程杰.清华大学出版社
-
《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社