查找算法之折半查找

折半查找算法的思路

首先查找的关键字在有序的查找表内, 这是折半查找的前提.(我们假设查找表内元素升序排列)
确定查找表中的范围,一般用两个下标来表示范围: left = 0,right = length -1
利用给定的关键字和查找表中的中间位置(mid = (left+right)/2)的元素比较,若相等,则查找成功,如待查找的元素比中间的元素大,我们让查找的范围变成中间到尾端(mid+1到right),如查找元素小于中间元素,我们就在头端到中间查找(left到mid-1).
然后一直这样重复的进行,直到找到或者范围缩小为空即查找失败.

分析折半查找的时间复杂度

下面我们来分析一下折半查找的平均查找长度,我们可以把折半查找过程用一棵二叉判定树来表示如下图

通过这样一棵数,我们可以计算出折半算法成功查找的平均查找长度
ASL = 11/6+22/6+3*3/6 = 7/3
无论查找是否成功,在有序表中查找某个关键字的过程,就是从根节点出发,走到该关键字对应节点的路径,而路径的长度就对应着查找长度.因此,折半查找的时间复杂度为O(log n)

折半查找的C语言实现

#include <stdio.h>int search(int (*), int, int);int main() {
int a[5] = {2,4,5,6,7};//初始化一个升序的数组;
printf("%d\n", search(a, 5, 7));//查找一个可以找到的元素;
printf("%d\n", search(a, 5, 8));
}int search(int *data, int length, int value) {
int left = 0, right = length - 1;
while (left<=right) {int mid = (left+right)/2;if (data[mid] == value) {return mid;//如果找到了.咱就直接返回元素的下标;}else if (data[mid] > value) {right = mid-1;//如何查找元素小于中间值,更新右坐标为mid-1;}else {left = mid+1;}
}
return -1;//如果循环结束没找到,我们返回-1;
}