本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- 分数的二分查找
- 判断分数/小数相等
题目
1.4.23 分数的二分查找。设计一个算法，使用对数级别的比较次数找出有理数 p/q，其中 0<p<q<N，比较形式为给定的数是否小于 x?提示：两个分母均小于N的有理数之差不小于1/N2。
1.4.23 Binary search for a fraction. Devise a method that uses a logarithmic number of queries of the form Is the number less than x? to find a rational number p/q such that 0 < p < q < N. Hint : Two fractions with denominators less than N cannot differ by more than 1/N2.
分析
程序员朋友都知道在我们的日常开发中，如果需要判断两个整数是否相等，可以使用"=="，但如果是判断两个分数是否相等，一般是小于某个数。这是因为在现有的计算机体系结构下，浮点数的精度是没有保障的，对于差别足够小的两个浮点数，我们一般只能认为它们是相等的，而无论他们是否真正相等。而对于一般情况，就是你看的教程说的，用一个足够小的数来比较他们的差值，如果差值小于这个足够小的数，如我上文所述，我们就只能接受一个事实就是，其实我们没法知道他们是不是相等，所以只能就当他们相等吧。这里的一个小问题是，这个足够小的数怎么定义？这个一般是个经验值，小数点后面七八个零一般认为就差不多了。
根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 1/N2。
答案
public class FractionBinarySearch {
public static int rank(double key, double[] a) { // 数组必须是有序的
int lo =0;
int hi = a.length - 1;
double threshold = 1.0 / (a.length * a.length);
while (lo <= hi){
int mid = lo + (hi - lo) / 2;
//这里的判断条件做个改动
if(Math.abs(a[mid] - key) <= threshold)
return mid;
else if(key > a[mid])
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
}
测试用例
public static void main(String[] args){
double[] fractions = {1.0/2.0,2.0/3.0,3.0/4.0,4.0/5.0,5.0/6.0};
Arrays.sort(fractions);
int index = rank(4.0/5.0,fractions);
System.out.print("4.0/5.0 在第" + index + "个");
}
代码索引
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
