如何用C++描述分块查找的算法

template<class Type>

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

{

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;

}

模板函数BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n个升序排列的元素中搜索x,找到x时返回其在数组中的位置，否则返回-1。容易看出，每执行一次while循环，待搜索数组的大小减少一半,因此整个算法在最坏情况下的时间复杂度为O(log n)。在数据量很大的时候，它的线性查找在时间复杂度上的优劣一目了然。
选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。

直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。

冒泡法
为了在a[1]中得到最大值，我们将a[1]与它后面的元素a[2]，a[3]，...，a[10]进行比较。首先比较a[1]与a[2]，如果a[1]<a[2]，则将a[1]与a[2]交换，否则不交换。这样在a[1]中得到的是a[1]与a[2]中的大数。然后将a[1]与a[3]比较，如果a[1]<a[3]，则将a[1]与a[3]交换，否则不交换。这样