2分查找的递归和非递归
二分查找的递归和非递归
二分查找,这个适用于已经排序好了的数组,没有排序那就先排序,不过要根据实际的情况,要是排序代价很小,这样很好了
/** *2.15,在有序数组中查找,利用二分查找的方法 * */ #include <iostream> using namespace std; /** *二分查找(也可以通过递归实现) * */ int sort(int *a, int length, int value){ int left = 0, right = length - 1; while(left <= right){ int center = (left + right)/2; if(value < a[center]){ right = center - 1; }else if(value > a[center]){ left = center + 1; }else{ return center; } } return -1; } //递归形式 int sort(int *a, int left, int right, int value){ int center = (left + right)/2; //异常时的检测 if(left == right && a[center] != value) return -1; //递归查找 if(value > a[center]) sort(a, center+1, right, value); else if(value < a[center]) sort(a, left, center-1, value); else return center; } int main(){ int a[10] = {2,4,5,6,8,12,32,45,55,65}; cout<<"列表:"<<endl; for(int i=0; i<10; i++){ cout<<a[i]<<" "; } cout<<endl; int v; cin>>v; cout<<"在位置:"<<sort(a, 10, v)<<endl; cout<<"递归在位置:"<<sort(a, 0,9, v)<<endl; }