对分查找

需求：给定一个整数X，求其在一个A₀， A₁，...， A_N-1，后者已经预先排序并在内存中，求使得A_i = X的下标 i，如果X不再数据中，则返回 i = -1。

1.最明显的解法是从左到右扫描数据，其运行花费线性时间。

2.一个好的策略是验证X是否是居中的元素。如果是，则答案就找到了。如果X小于居中元素，那么我们可以应用同样的策略于居中元素左边已排序的子序列；如果大于，同理用于右边已排序的子序列。

int BinarySearch(const ElementType A[], ElementType X, int N) {
    int Low, Mid, High;
    Low = 0, High = N - 1;
    while(Low <= Hight) 
    {
        Mid = (Low + High) / 2;
        if (A[Mid] < X)
            Low = Mid + 1;
        else if (A[Mid] > X) 
            High = Mid - 1;
        else 
            return Mid;
    }
    return NotFound;
}