折半查找法

折半查找要求线性表是有序的，即表中记录按关键字排序。

代码：

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