二叉树搜索（二分查找法）

 

非递归方式：

// 二分查找法,在有序数组arr中,查找target // 如果找到target,返回相应的索引index // 如果没有找到target,返回-1 template<typename T> int binarySearch(T arr[], int n, T target){ // 在arr[l...r]之中查找target int l = 0, r = n-1; while( l <= r ){ //int mid = (l + r)/2; int mid = l + (r-l)/2; if( arr[mid] == target ) return mid; if( arr[mid] > target ) r = mid - 1; else l = mid + 1; } return -1; }

 

递归方式：

template<typename T> int __binarySearch2(T arr[], int l, int r, T target){ if( l > r ) return -1; int mid = (l+r)/2; if( arr[mid] == target ) return mid; else if( arr[mid] > target ) return __binarySearch2(arr, 0, mid-1, target); else return __binarySearch2(arr, mid+1, r, target); }

 

template<typename T> int binarySearch2(T arr[], int n, T target){ return __binarySearch2( arr , 0 , n-1, target); }

 

                  

转载于:https://www.cnblogs.com/lzb0803/p/9192969.html