折半查找法
折半查找要求线性表是有序的，即表中记录按关键字排序。
代码：
int BinarySearch(int array[], int low, int high, int k) {
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (k < array[mid])
high = mid - 1;
else if (k > array[mid])
low = mid + 1;
else
return mid + 1;
}
return 0;
}
ASL分析：
折半查找的过程可以用二叉树来表示，把当前查找区间中的中间位置上的记录作为树根，左子表和右子表中的记录分别作为根的左子树和右子树，由此得到的二叉树称为折半查找判定树。
例如有序序列：{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
可以构建如下判定树：
折半查找判定树.png
由折半查找判定树可以求得ASL：
上图中ASL = （3+4+2+3+4+1+3+4+2+4+3+4）/12
网友评论