折半查找又稱二分法查找，查找的過程是先確定待查找數的范圍區間，然后逐步縮小查找范圍，直到找到或找不到為止。
假設現有一有序數組: [ 3, 5, 8, 13, 15, 16, 20, 27, 31, 56 ]，則查找關鍵字 20 的過程如下:
C++ 實現代碼片段
//二分法查找/折半查找
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){ //找到,返回下標索引值
return middle;
}else if(array[middle] > key){ //查找值在低半區
high = middle - 1;
}else{ //查找值在高半區
low = middle + 1;
}
}
return -1; //找不到
}
Java 實現代碼片段
//二分法查找/折半查找
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){ //找到,返回下標索引值
return middle;
}else if(array[middle] > key){ //查找值在低半區
high = middle - 1;
}else{ //查找值在高半區
low = middle + 1;
}
}
return -1; //找不到
}
posted on 2013-02-06 18:34
fancydeepin 閱讀(2768)
評論(0) 編輯 收藏