时间复杂度为 (log n) 的二分查找函数

Question

例如，

print(binary_search(7, [1, 5, 10])) # 2 
print(binary_search(42, (-5, 1, 3, 5, 7, 10))) # 6

我的代码：

def binary_search(x, seq):
    if len(seq) == 0
    low = 0
    high = len(seq)
    mid = (low+high)//2
    if x == seq[mid]:
       return mid
    elif x < seq[mid]:
         return binary_search(x,seq[:mid])
    elif x > seq[mid]:
         return mid + 1 + binary_search(x,seq[mid+1:]

Answer 1

没什么，第二行缺少一个冒号和一个 return 语句，最后一行缺少一个结束括号：

def binary_search(x, seq):
    if len(seq) == 0: return 0
    low = 0
    high = len(seq)
    mid = (low+high)//2
    if x == seq[mid]:
        return mid
    elif x < seq[mid]:
        return binary_search(x,seq[:mid])
    elif x > seq[mid]:
        return mid + 1 + binary_search(x,seq[mid+1:])

print(binary_search(7, [1, 5, 10]))  # 2
print(binary_search(42, (-5, 1, 3, 5, 7, 10)))  # 6

值得注意的是，有一个 stdlib 模块用于此目的：bisect.bisect_left()

假设 a 已经排序，返回值适合用作 list.insert() 的第一个参数。

参数的顺序正好相反：

import bisect
print(bisect.bisect_left([1, 5, 10], 7))  # 2
print(bisect.bisect_left((-5, 1, 3, 5, 7, 10), 42))  # 6