折半查找又稱二分法查找，查找的過程是先確定待查找數(shù)的范圍區(qū)間，然后逐步縮小查找范圍，直到找到或找不到為止。
假設(shè)現(xiàn)有一有序數(shù)組: [ 3, 5, 8, 13, 15, 16, 20, 27, 31, 56 ]，則查找關(guān)鍵字 20 的過程如下:
C++ 實現(xiàn)代碼片段
//二分法查找/折半查找
int binarySearch(Element array[], int len, int key){
int low = 0, high = len - 1, middle;
while(low <= high){
middle = (low + high) / 2;
if(array[middle] == key){ //找到,返回下標(biāo)索引值
return middle;
}else if(array[middle] > key){ //查找值在低半?yún)^(qū)
high = middle - 1;
}else{ //查找值在高半?yún)^(qū)
low = middle + 1;
}
}
return -1; //找不到
}
Java 實現(xiàn)代碼片段
//二分法查找/折半查找
public static int binarySearch(int[] array, int key){
int low = 0, high = array.length - 1, middle;
while(low <= high){
middle = (low + high) / 2;
if(array[middle] == key){ //找到,返回下標(biāo)索引值
return middle;
}else if(array[middle] > key){ //查找值在低半?yún)^(qū)
high = middle - 1;
}else{ //查找值在高半?yún)^(qū)
low = middle + 1;
}
}
return -1; //找不到
}
posted on 2013-02-06 18:34
fancydeepin 閱讀(2770)
評論(0) 編輯 收藏