|
在面試的時候二分查找是用的比較多一種查找算法,，如何在面試官面前快速準確得的寫出代碼決定你是否能夠被錄取。以前一直以為二分查找很簡單，所以就沒怎么重視,，但是真要在面試官面前對著黑板手寫出來,，還是漏洞百出。今天自己在電腦面前敲出了二分查找的代碼,，也花了將近半個小時,。對于這種基礎排序查找算法，還是得好好重視,。
二分查找可以使用遞歸和非遞歸的方法來解決,，下面給出代碼實例,。  View
Code
 #include #include using namespace std; //不適用遞歸，如果存在返回數(shù)組位置,，不存在則返回-1 int BinarySearch(int arry[],int len,int value) { //如果傳入的數(shù)組為空或者數(shù)組長度<=0那么就返回-1,。防御性編程 if(arry==NULL||len<=0) return -1; int start=0; int end=len-1; while(start<=end)//判斷清是否有= { int mid=start+(end-start)/2; if(arry[mid]==value) return mid; else if(value<</FONT>arry[mid])
else start=mid+1; } return -1; } //改進思路:1.不要傳參，而是傳引用調用,，減少垃圾 // 2.使用模板 int BinarySearchRecursion(int arry[],int value,int start,int end) { if(start>end)
return -1; int mid=start+(end-start)/2; if(arry[mid]==value) return mid; else if(value<arry[mid]) return BinarySearchRecursion(arry,value,start,mid-1); else return BinarySearchRecursion(arry,value,mid+1,end);
int BinarySearchRecursion(int arry[],int len,int value) { //如果傳入的數(shù)組為空或者數(shù)組長度<=0那么就返回-1,。防御性編程 if(arry==NULL||len<=0) return -1; return BinarySearchRecursion(arry,value,0,len-1); } void main() { int arry[]={1,2,3,4,5,6,7,8}; int len=sizeof(arry)/sizeof(int); int index=BinarySearch(arry,len,4);
int index2=BinarySearchRecursion(arry,len,9);
} 在上述遞歸的二分查找方法中： int BinarySearchRecursion(int arry[],int value,int start,int end) 我們可以發(fā)現(xiàn)這個方法中的后三個參數(shù)value，start,，end采用的是傳值調用,，只有第一個參數(shù)arry是傳址調用。我們知道在效率方面,，傳值調用要比傳址調用來的低,，因為傳值調用要進行一次變量的拷貝，而傳址調用則是直接對這個變量進行操作,。因此這里我們可以將后面的三個參數(shù)改為傳址調用 改進后的代碼實例如下： View
Code
int BinarySearchRecursion(int arry[],int &value,int &start,int &end) { if(start>end) return -1; int mid=start+(end-start)/2; if(arry[mid]==value) return mid; else if(value<arry[mid]) {
return BinarySearchRecursion(arry,value,start,end);
else {
return BinarySearchRecursion(arry,value,start,end); } } int BinarySearchRecursion(int arry[],int &len,int &value) { //如果傳入的數(shù)組為空或者數(shù)組長度<=0那么就返回-1,。防御性編程 if(arry==NULL||len<=0) return -1; int start=0; int end=len-1; return BinarySearchRecursion(arry,value,start,end); } void main() { int arry[]={1,2,3,4,5,6,7,8}; int len=sizeof(arry)/sizeof(int); int especteNum1=4; int especteNum2=9; int index=BinarySearch(arry,len,especteNum1);
int index2=BinarySearchRecursion(arry,len,especteNum2);
} |
|
|
來自： 昵稱13397030 > 《待分類1》
