本系列博客習(xí)題來自《算法(第四版)》，算是本人的讀書筆記，如果有人在讀這本書的，歡迎大家多多交流。為了方便討論，本人新建了一個(gè)微信群(算法交流)，想要加入的，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識點(diǎn)

• 分?jǐn)?shù)的二分查找
• 判斷分?jǐn)?shù)/小數(shù)相等

題目

1.4.23 分?jǐn)?shù)的二分查找。設(shè)計(jì)一個(gè)算法，使用對數(shù)級別的比較次數(shù)找出有理數(shù) p/q，其中 0<p<q<N，比較形式為給定的數(shù)是否小于 x?提示：兩個(gè)分母均小于N的有理數(shù)之差不小于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².

分析

程序員朋友都知道在我們的日常開發(fā)中，如果需要判斷兩個(gè)整數(shù)是否相等，可以使用"=="，但如果是判斷兩個(gè)分?jǐn)?shù)是否相等，一般是小于某個(gè)數(shù)。這是因?yàn)樵诂F(xiàn)有的計(jì)算機(jī)體系結(jié)構(gòu)下，浮點(diǎn)數(shù)的精度是沒有保障的，對于差別足夠小的兩個(gè)浮點(diǎn)數(shù)，我們一般只能認(rèn)為它們是相等的，而無論他們是否真正相等。而對于一般情況，就是你看的教程說的，用一個(gè)足夠小的數(shù)來比較他們的差值，如果差值小于這個(gè)足夠小的數(shù)，如我上文所述，我們就只能接受一個(gè)事實(shí)就是，其實(shí)我們沒法知道他們是不是相等，所以只能就當(dāng)他們相等吧。這里的一個(gè)小問題是，這個(gè)足夠小的數(shù)怎么定義？這個(gè)一般是個(gè)經(jīng)驗(yàn)值，小數(shù)點(diǎn)后面七八個(gè)零一般認(rèn)為就差不多了。
根據(jù)書中的提示，將二分查找中判斷相等的條件改為兩個(gè)數(shù)的差小于等于 1/N²。

答案

public class FractionBinarySearch {
    public static int rank(double key, double[] a) { // 數(shù)組必須是有序的
        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;
            //這里的判斷條件做個(gè)改動
            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 + "個(gè)");
    }

代碼索引

FractionBinarySearch.java

廣告

我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載。