从有序序列中求最大 不大于目标 的数的下标的二分查找怎么写比较优雅？

Question

本身这个题挺简单的，但是如果增加这样一个要求怎么写：如果序列中有多个等于目标的数，则可以传入一个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]

Answer 1

我后来又想了想，同时参考了楼上@brayden的思想，把两种功能的实现完全分开，重新写了一个
defbinsearchmax(a,target):
l,r=0,len(a)-1
while(lmid=l+(r-l)/2
ifa[mid]<=target:
l=mid
else:
r=mid-1
ifa[r]<=target:returnr
ifa[l]<=target:returnl
return-1
defbinsearchmin(a,target):
l,r=0,len(a)-1
while(lmid=l+(r-l)/2
ifa[mid]l=mid
else:
r=mid
ifa[l]==target:returnl
ifa[r]==target:returnr
ifa[r]ifa[l]return-1
defbinsearch(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