Java 算法之折半查找法
算法介绍
折半查找法要求线性表是有序的，即表中记录按关键字有序（假设是递增有序的）。
折半查找的基本思路：设 R[low, ···, high] 是当前的查找区间，首先确定该区间的中间位置 mid = (low + high) / 2，然后将待查的 k 值与 R[mid] 比较，若相等，则查找成功，并返回该位置，否则需确定新的查找区间。若 R[mid] > k，则由表的有序性可知 R[mid, ···, high] 均大于k，因此若表中存在关键字等于 k 的记录，则该记录必定是在 mid 左边的子表 R[low, ···, mid - 1] 中，故新的查找区间是左子表 R[low, ···, mid - 1] 。类似地，若 R[mid] < k，则要查找的 k 必在 mid 的右子表 R[mid + 1, ···, high]中，即新的查找区间是右子表 R[mid + 1, ···, high] 。递归地处理新区间，直到子区间的长度小于 1 时查找过程结束。
折半查找法算法常规代码
public static int bSearch(int R[], int low, int high, int k){
int mid;
while(low <= high){ //当子表长度大于等于1时进行循环
mid = (low + high) / 2; //取当前表的中间位置
if(R[mid] == k) //找到后返回元素的位置
return mid;
else if(R[mid] > k) //说明需要在R[low,···,mid-1]中查找
high = mid - 1;
else //说明需要在R[mid+1,···,high]中查找
low = mid + 1;
}
return 0; //查找不成功则返回0，数组R[]从下标1开始存，查找失败返回0
}
折半查找的过程可以用二叉树来标识。把当前查找区间中的中间位置上的记录作为树根，左子表和右子表中的记录分别作为根的左子树和右子树，由此得到的二叉树称为描述折半查找的判定树。
折半查找法算法的两种速记代码
public static int bSearch_1(int[] arr, int key){
int min, max, mid;
min = 0;
max = arr.length - 1;
mid = (max + min) / 2;
while(arr[mid] != key){
if(key > arr[mid])
min = mid + 1;
else if(key < arr[mid])
max = mid - 1;
if(min > max)
return -1;
mid = (max + min) / 2;
}
return mid;
}
public static int bSearch_2(int[] arr, int key){
int min = 0, max = arr.length - 1, mid;
while(min <= max){
mid = (max + min) / 2;
if(key > arr[mid])
min = mid + 1;
else if(key < arr[mid])
max = mid - 1;
else
return mid;
}
return -1;
}
