【背景】
二分查找也称折半查找（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较大时，可近似看做：
因此，折半查找的时间复杂度为
【总结】
折半查找的优点是：比较次数少，查找效率高。
其缺点是：对表结构要求高，只能用于顺序存储的有序表。而有序表的构造需要付出较大的时间代价。
因此，折半查找不适用于数据元素经常变动的线性表。
【参考文献】
-
《大话数据结构》.程杰.清华大学出版社
-
《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社