[转]编程珠玑第五章二分搜索(折半查找)之java实现

http://blog.csdn.net/hwe_xc/article/details/51813080

二分搜索又称为折半查找,用来高效快速的解决如下问题:

我们需要确定排序后的数组x[0..n-1] 中是否包含目标元素t。 说的准确一点,就是已知
n>=0且x[0]<=x[1]<=x[2]…<=x[n-1],当n=0时数组为空,t与x中元素的数据类型相同。答案存在一个整数中,为-1则不在x数组中,否则返回具体位置0~n-1。

此问题看起来是个很小的问题,其实也不容易。据说第一篇二分搜索论文是1946年发表,但是对于完全没有错误的二分搜索程序却是在1962年才出现,用了16年的时间。可想而知,要想写出一个基本没有错误的程序不是那么简单的事儿。

下面列出此程序需要注意的地方

注意点

1. 一定要对数组进行排序

2. 如果被搜索的项不在数组中,需要返回 -1

3. 如果被搜索项多次出现,是否有特殊需求,比如需要返回第一次出现的位置

代码实现

/**
* 在排序好的数组中通过二分搜索t的位置(对于t重复出现不要求找出特定位置)
*
* @param a
* 排序好的数组
* @param t
* 被查找项
* @return
*/
public int binarySearch(int a[], int t) {
int i = 0, j = a.length - 1;
int result = -1; while (i <= j) {
// 取得中间值
int m = (i + j) / 2;
// 被查找项大于中间值
if (t > a[m]) {
// 查找 m + 1 ~ j 区间
// 注意:一定是 m + 1开始,如果是m,有可能会陷入死循环之中
i = m + 1;
// 被查找项小于中间值
} else if (t < a[m]) {
// 查找 i ~ m - 1 区间
// 注意:一定是 m - 1结束,如果是m,有可能会陷入死循环之中
j = m - 1;
} else {
// 被查找项等于中间值, 直接返回
result = m;
break;
}
}
return result;
}

上面的代码是二分查找的一般形式,对于在t重复出现情况下没要求的话,完全够用了。如果需要返回第一次t出现的位置,我们又该如何写,请看下面代码:

public static int binarySearchFirstIndex(int a[], int t) {
int i = 0, j = a.length - 1;
int result = -1; while (i <= j) {
// 取得中间值
int m = (i + j) / 2;
// 被查找项大于中间值
if (t > a[m]) {
// 查找 m + 1 ~ j 区间
// 注意:一定是 m + 1开始,如果是m,有可能会陷入死循环之中
i = m + 1;
// 被查找项小于中间值
} else if (t < a[m]) {
// 查找 i ~ m - 1 区间
// 注意:一定是 m - 1结束,如果是m,有可能会陷入死循环之中
j = m - 1;
} else {
// 被查找项等于中间值, 结果等于中间值
result = m;
// 附加判断中间值的左边值是否等于t
// 注意m > 0,如果不判断可能引起数组下表越界
if (m > 0 && t == a[m - 1]) {
// 继续查找
j = m - 1;
} else {
break;
}
}
}
return result;
}

可以看到,上面代码有一点小小的改进,会去判断中间值是否等于其左边的值,如果等于继续查找。对于查找最后一个位置,原理类似。

上一篇:Vue项目


下一篇:donet core 应用 部署到CentOS