“二分查找”的版本间的差异
跳到导航
跳到搜索
Jihongchang（讨论 | 贡献） |
Jihongchang（讨论 | 贡献） |
||
| 第2行： | 第2行： | ||
public class BinarySearch { | public class BinarySearch { | ||
| − | public static int rank(int key, int[] a) { | + | public static int rank(int key, int[] a) { |
//数组必须是有序的 | //数组必须是有序的 | ||
int lo = 0; | int lo = 0; | ||
2024年11月14日 (四) 08:54的最新版本
public class BinarySearch {
public static int rank(int key, int[] a) {
//数组必须是有序的
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
//被查找的键要么不存在，要么必然存在于a[lo...hi]之中
int mid = lo + (hi - lo) /2;
if (key < a[mid]) {
hi = mid - 1; //-1：从候选中过滤掉已经判断过的元素
} else if (key > a[mid]) {
lo = mid + 1; //+1：从候选中过滤掉已经判断过的元素
} else {
return mid;
}
}
return -1;
}
}