本身这个题挺简单的,但是如果增加这样一个要求怎么写:
如果序列中有多个等于目标的数,则可以传入一个flag参数,来决定返回等于目标的数最大下标还是最小下标
举个例子:
binsearch([1, 3, 3], 3, "max") 返回 2
binsearch([1, 3, 3], 3, "min") 返回 1
binsearch([1, 1], 2, "max") 和 binsearch([1, 1], 2, "min") 都返回 1
就是只有当数列中有多个等于目标的数时flag参数才有意义。
我写的只考虑flag=="min"的代码,我觉得最后几行if已经很不优雅了,flag=="max"怎么也写不对
def binsearch(a, target, flag="min"):
''' Find the index of the max one not greater than target'''
l, r = 0, len(a)-1
while (l < r-1):
mid = l + (r-l) / 2
if a[mid] >= target:
r = mid
else:
l = mid+1
if a[l] == target: return l
if a[r] == target: return r
if a[r] < target: return r
if a[l] < target: return l
return -1
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") == 0)
# 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)
# print binsearch([1, 3, 5, 5], 5, "max")
# assert(binsearch([1, 3, 5, 5], 5, "max") == 3)
我后来又想了想,同时参考了楼上@brayden 的思想,把两种功能的实现完全分开,重新写了一个
我自己构造的测试数据全部通过了。总结一下,我觉得我一开始试图把两种功能的逻辑混到一起的这个思想是导致我写不出来的一个重要原因。再次感谢楼上的@brayden