01-复杂度3 二分查找 (20 分)

本题要求实现二分查找算法。

模板很好理解。

Position BinarySearch( List L, ElementType X )
{
    int l = 1, r = L->Last;
    int mid;
    while(l < r - 1) //由于整数除法的局限性，只能将要找的数精确到2个数之间。
        {
            mid = (l + r) / 2;
            if(L -> Data[mid] > X)
                {
                    r = mid;
                }
            else l = mid;
        }
    //看看到底是左边那个数还是右边那个数满足题意
    if(L -> Data[l] == X) return l;
    else if(L -> Data[r] == X) return r;
    return NotFound;
}