分治-二分搜索

给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

据此容易设计出二分搜索算法：

template

int BinarySearch(Typea[], constType& x, int l, int r)

{

     while (r >= l){

        int m = (l+r)/2;

        if (x == a[m]) return m;

        if (x

        }

    return -1;

} 

算法复杂度分析：

每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn) 次。

循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。