Chapter2: 時間復雜度分析、遞歸赖阻、查找與排序
3. 二分查找的遞歸與非遞歸實現(xiàn)
二分查找即折半查找，為查找算法的一種苇侵，思路為先將數(shù)組排序榆浓，再通過不斷與中值比較將查找范圍減半，最終找到目標
一個小技巧：
mid=(min+max)/2; 等價于 min+(max-min)/2 ,這樣寫能防止min+max溢出; 寫為位運算 min=min+(max-min)>>1 的形式更高效
非遞歸實現(xiàn)
/*非遞歸實現(xiàn)二分查找
參數(shù):有序數(shù)組arr,數(shù)組元素個數(shù)arrLen,帶查找數(shù)字num
返回:找到則返回所在數(shù)組下標萍鲸，找不到則返回-1
*/
int biSearch(int* arr,int arrLen,int num){
int min=0;
int max=arrLen-1;
int mid;
while(min<=max)
{
mid=(min+max)/2;//等價于min+(max-min)/2,這樣寫能防止min+max溢出，寫為位運算min=min+(max-min)>>1的形式更高效
if(num<arr[mid]){
max=mid-1;
}
else if(num>arr[mid]){
min=mid+1;
}
else
return mid;
}
return -1;//未找到
}
遞歸實現(xiàn)
/*遞歸實現(xiàn)二分查找
參數(shù):有序數(shù)組地址arr,查找范圍的最小下標minSub，查找范圍的最大下標maxSub帶查找數(shù)字num
返回:找到則返回所在數(shù)組下標秽五，找不到則返回-1
*/
int biSearch2(int* arr,int minSub,int maxSub,int num){
if(minSub>maxSub){
return -1;//找不到num時的出口
}
int mid=(minSub+maxSub)/2;
if(num<arr[mid]){
return biSearch2(arr,minSub,mid-1,num);
}
else if(num>arr[mid]){
return biSearch2(arr,mid+1,maxSub,num);
}
else{
return mid;//找到num時的出口
}
}
參考資料
[1] 二分查找遞歸與非遞歸解法
