算法练习(76): 分数的二分查找(1.4.23)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 分数的二分查找
• 判断分数/小数相等

题目

1.4.23 分数的二分查找。设计一个算法，使用对数级别的比较次数找出有理数 p/q，其中 0<p<q<N，比较形式为给定的数是否小于 x?提示：两个分母均小于N的有理数之差不小于1/N²。

---

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/N².

分析

程序员朋友都知道在我们的日常开发中，如果需要判断两个整数是否相等，可以使用"=="，但如果是判断两个分数是否相等，一般是小于某个数。这是因为在现有的计算机体系结构下，浮点数的精度是没有保障的，对于差别足够小的两个浮点数，我们一般只能认为它们是相等的，而无论他们是否真正相等。而对于一般情况，就是你看的教程说的，用一个足够小的数来比较他们的差值，如果差值小于这个足够小的数，如我上文所述，我们就只能接受一个事实就是，其实我们没法知道他们是不是相等，所以只能就当他们相等吧。这里的一个小问题是，这个足够小的数怎么定义？这个一般是个经验值，小数点后面七八个零一般认为就差不多了。
根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 1/N²。

答案

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 + "个");
    }

代码索引

FractionBinarySearch.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。