本系列博客習(xí)題來(lái)自《算法(第四版)》惦辛，算是本人的讀書筆記痪欲，如果有人在讀這本書的悦穿，歡迎大家多多交流。為了方便討論业踢，本人新建了一個(gè)微信群(算法交流)栗柒，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝知举。另外瞬沦，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論
知識(shí)點(diǎn)
- 分?jǐn)?shù)的二分查找
- 判斷分?jǐn)?shù)/小數(shù)相等
題目
1.4.23 分?jǐn)?shù)的二分查找雇锡。設(shè)計(jì)一個(gè)算法逛钻，使用對(duì)數(shù)級(jí)別的比較次數(shù)找出有理數(shù) p/q，其中 0<p<q<N锰提，比較形式為給定的數(shù)是否小于 x?提示：兩個(gè)分母均小于N的有理數(shù)之差不小于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.
分析
程序員朋友都知道在我們的日常開發(fā)中羡洁，如果需要判斷兩個(gè)整數(shù)是否相等袜炕，可以使用"=="，但如果是判斷兩個(gè)分?jǐn)?shù)是否相等，一般是小于某個(gè)數(shù)冯吓。這是因?yàn)樵诂F(xiàn)有的計(jì)算機(jī)體系結(jié)構(gòu)下窟蓝，浮點(diǎn)數(shù)的精度是沒有保障的挠阁，對(duì)于差別足夠小的兩個(gè)浮點(diǎn)數(shù)乱灵，我們一般只能認(rèn)為它們是相等的，而無(wú)論他們是否真正相等文黎。而對(duì)于一般情況惹苗，就是你看的教程說(shuō)的，用一個(gè)足夠小的數(shù)來(lái)比較他們的差值耸峭，如果差值小于這個(gè)足夠小的數(shù)桩蓉，如我上文所述，我們就只能接受一個(gè)事實(shí)就是劳闹，其實(shí)我們沒法知道他們是不是相等院究，所以只能就當(dāng)他們相等吧。這里的一個(gè)小問(wèn)題是本涕，這個(gè)足夠小的數(shù)怎么定義业汰？這個(gè)一般是個(gè)經(jīng)驗(yàn)值，小數(shù)點(diǎn)后面七八個(gè)零一般認(rèn)為就差不多了菩颖。
根據(jù)書中的提示样漆，將二分查找中判斷相等的條件改為兩個(gè)數(shù)的差小于等于 1/N2。
答案
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è)改動(dòng)
if(Math.abs(a[mid] - key) <= threshold)
return mid;
else if(key > a[mid])
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
}
測(cè)試用例
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è)");
}
代碼索引
廣告
我的首款個(gè)人開發(fā)的APP壁紙寶貝上線了晦闰，歡迎大家下載放祟。
