关于#算法#的问题，如何解决？

Question

给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。

Answer 1

template<class Type>

int BinarySearch(Type a[], const Type& x, int n)

{//在a[0:n]中搜索x，找到x时返回其在数组中的位置，否则返回-1

     Int left=0;  int  right=n-1;

     While (left<=right){

        int middle=(left+right)/2;

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

        if (x>a[middle]) left=middle+1;

        else right=middle-1;

      }

      Return -1;

}

时间复杂性为O(logn)