星期二, 10月 10, 2006

水準上的差異

前幾天課堂上教了使用recursive的 binary search (在有序區間),於是,我照了自己的想法來寫一個簡單的function


bool BinarySearch(int* a, int left, int right,const int SearchValue){
if(left==right){
if(a[left]=SearchValue) return true;
else return false;
}
else if(left int pivot=(left+right)/2;

if(a[pivot]==SearchValue) return true;
else if(a[pivot]>SearchValue) BinarySearch(a,left,pivot,SearchValue);
else BinarySearch(a,pivot,right,SearchValue);
}
else ;
}


再來看看我參考STL源碼剖析的p.376 lower_bound function 的改良寫法

bool BinarySearch(int *a,int left,int right,int value){
int len=right-left;
while(len>0){
int half = len >> 1; /* half/=2 */
int middle = left + half;

if(a[middle]==value){
left=middle;
break;
}
else if(a[middle]< value){
left = middle+1;
len = len - half - 1;
}
else len = half;
}

if(a[left]==value) return true;
else return false;
}



技巧可謂高下立判

張貼留言