二分查找、折半查找、递归与非递归

1、非递归方法

template <typename T> int BinarySearch(T array[],int low,int high,T key) { while(low <= high) { int mid = low + (high-low)/2; if (key < array[mid] ) high = mid - 1; else if ( key > array[mid]) low = mid+1; else return mid; } return -1; }

2、递归方法

template <typename T> int BinarySearch2(T array[],int low,int high,T key) { if(low <= high) { int mid = low + (high-low)/2; if ( key < array[mid] ) return BinarySearch2(array,low,mid-1,key); else if ( key > array[mid] ) return BinarySearch2(array,mid+1,high,key); else return mid; } return -1; }