折半查找,又稱作二叉搜索,是面試時(shí)經(jīng)常問到的算法問題,今天我們來(lái)看一下它的非遞歸和遞歸方法.
在有序表中日裙，把待查找數(shù)據(jù)值與查找范圍的中間元素值進(jìn)行比較，會(huì)有三種情況出現(xiàn)：
1） 待查找數(shù)據(jù)值與中間元素值正好相等刃麸，則放回中間元素值的索引。
2） 待查找數(shù)據(jù)值比中間元素值小，則以整個(gè)查找范圍的前半部分作為新的查找范圍异赫，執(zhí)行1），直到找到相等的值头岔。
3） 待查找數(shù)據(jù)值比中間元素值大塔拳，則以整個(gè)查找范圍的后半部分作為新的查找范圍，執(zhí)行1）峡竣，直到找到相等的值
4） 如果最后找不到相等的值靠抑，則返回錯(cuò)誤提示信息。
按照二叉樹來(lái)理解：中間值為二叉樹的根适掰，前半部分為左子樹颂碧，后半部分為右子樹。折半查找法的查找次數(shù)正好為該值所在的層數(shù)类浪。等概率情況下载城，約為log2(n+1)-1
- 非遞歸方法
int BinTree(int Array[],int arrayLength,int key){
int min = 0, max = arrayLength;
int mid;
while (min <= max) {
mid = (min + max) / 2;
if (key == Array[mid]) {
return mid;
}
if (key < Array[mid]) {
max = mid-1;
}else if(key > Array[mid]){
min = mid+1;
}
}
return -1;
}
- 遞歸方法
int BinTree(int Array[],int min,int max,int key){
if(min <= max){
int mid = (min + max) / 2;
if (key == Array[mid]) {
return mid;
}else if(key < Array[mid]){
return BinTree(Array, min, mid-1, key);
}else if(key > Array[mid]){
return BinTree(Array, mid+1, max, key);
}
}
return -1;
}
