折半查找又称二分法查找，查找的过程是先确定待查找数的范围区间，然后逐步缩小查找范围，直到找到或找不到为止。
假设现有一有序数组: [ 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 阅读(2763)
评论(0) 编辑 收藏