首頁猿問從有序序列中求最大不大于目標(biāo)...

從有序序列中求最大不大于目標(biāo) 的數(shù)的下標(biāo)的二分查找怎么寫比較優(yōu)雅？

JavaScript

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

本身這個題挺簡單的，但是如果增加這樣一個要求怎么寫：如果序列中有多個等于目標(biāo)的數(shù)，則可以傳入一個flag參數(shù)，來決定返回等于目標(biāo)的數(shù)最大下標(biāo)還是最小下標(biāo)舉個例子：binsearch([1,3,3],3,"max")返回2binsearch([1,3,3],3,"min")返回1binsearch([1,1],2,"max")和binsearch([1,1],2,"min")都返回1就是只有當(dāng)數(shù)列中有多個等于目標(biāo)的數(shù)時flag參數(shù)才有意義。我寫的只考慮flag=="min"的代碼，我覺得最后幾行if已經(jīng)很不優(yōu)雅了，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條經(jīng)驗獲得超3個贊

我后來又想了想，同時參考了樓上@brayden的思想，把兩種功能的實現(xiàn)完全分開，重新寫了一個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)我自己構(gòu)造的測試數(shù)據(jù)全部通過了?？偨Y(jié)一下，我覺得我一開始試圖把兩種功能的邏輯混到一起的這個思想是導(dǎo)致我寫不出來的一個重要原因。再次感謝樓上的@brayden