首頁猿問從有序序列中求最大不大于目標...

從有序序列中求最大不大于目標的數的下標的二分查找怎么寫比較優雅？

JavaScript

幕布斯6054654 2019-04-19 16:13:09

本身這個題挺簡單的，但是如果增加這樣一個要求怎么寫：如果序列中有多個等于目標的數，則可以傳入一個flag參數，來決定返回等于目標的數最大下標還是最小下標舉個例子：binsearch([1,3,3],3,"max")返回2binsearch([1,3,3],3,"min")返回1binsearch([1,1],2,"max")和binsearch([1,1],2,"min")都返回1就是只有當數列中有多個等于目標的數時flag參數才有意義。我寫的只考慮flag=="min"的代碼，我覺得最后幾行if已經很不優雅了，flag=="max"怎么也寫不對defbinsearch(a,target,flag="min"):'''Findtheindexofthemaxonenotgreaterthantarget'''l,r=0,len(a)-1while(l=target:r=midelse:l=mid+1ifa[l]==target:returnlifa[r]==target:returnrifa[r]

查看完整描述

2 回答

慕森王

TA貢獻1777條經驗獲得超3個贊

我后來又想了想，同時參考了樓上@brayden的思想，把兩種功能的實現完全分開，重新寫了一個defbinsearchmax(a,target):l,r=0,len(a)-1while(lmid=l+(r-l)/2ifa[mid]<=target:l=midelse:r=mid-1ifa[r]<=target:returnrifa[l]<=target:returnlreturn-1defbinsearchmin(a,target):l,r=0,len(a)-1while(lmid=l+(r-l)/2ifa[mid]l=midelse:r=midifa[l]==target:returnlifa[r]==target:returnrifa[r]ifa[l]return-1defbinsearch(a,target,flag="min"):ifflag=="min":returnbinsearchmin(a,target)else:returnbinsearchmax(a,target)assert(binsearch([1,3],1)==0)assert(binsearch([1,3],3)==1)assert(binsearch([1,3],2)==0)assert(binsearch([1,1],2)==1)assert(binsearch([1,1,3],1)==0)assert(binsearch([2,2],1)==-1)assert(binsearch([1,3,5],1)==0)assert(binsearch([1,3,5],5)==2)assert(binsearch([1,3,5,5],5)==2)assert(binsearch([1,1,1,2,2,2,3,4,5,5],2)==3)assert(binsearch([1,3],1,"max")==0)assert(binsearch([1,3],3,"max")==1)assert(binsearch([1,3],2,"max")==0)assert(binsearch([1,1],2,"max")==1)assert(binsearch([1,1,3],1,"max")==1)assert(binsearch([2,2],1,"max")==-1)assert(binsearch([1,3,5],1,"max")==0)assert(binsearch([1,3,5],5,"max")==2)assert(binsearch([1,3,5,5],5,"max")==3)我自己構造的測試數據全部通過了。總結一下，我覺得我一開始試圖把兩種功能的邏輯混到一起的這個思想是導致我寫不出來的一個重要原因。再次感謝樓上的@brayden

反對回復 2019-04-19

2 回答
0 關注
1029 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

從有序序列中求最大 不大于目標 的數的下標的二分查找怎么寫比較優雅？

從有序序列中求最大 不大于目標 的數的下標的二分查找怎么寫比較優雅？

2 回答

添加回答

從有序序列中求最大不大于目標的數的下標的二分查找怎么寫比較優雅？

從有序序列中求最大不大于目標的數的下標的二分查找怎么寫比較優雅？