Python2二进制搜索

Question

我想尝试实现二进制搜索，下面是我的想法。从代码清晰的角度或代码优化的角度来看，还有什么可以做得更好的吗？如果有任何批评意见，我们将不胜感激：

import random
# implement a binary search

def binary_search(alist, item):
    first = 0
    last = len(alist)-1
    found = False
    midpoint = None
    while True:
        midpoint = first + ((last-first) // 2)
        if alist[midpoint] == item:
            return midpoint
        elif alist[midpoint] < item:
            first = midpoint
        elif alist[midpoint] > item:
            last = midpoint

def _create_search_criteria(cap=10000):
    # choose a target to search for
    choice = random.randrange(0, cap/2)
    # create some data full of random numbers
    data = [random.randrange(0, cap/2) for i in xrange(cap)]
    # ensure the choice is nowhere in the data
    data = [d for d in data if d != choice]
    # put a single of instance of choice back into the data
    data[random.randrange(0, cap)] = choice
    # sort the data
    data = sorted(data)
    return data, choice

def test_binary_search():
    data, choice = _create_search_criteria()
    print 'Searching for: ' + str(choice)
    index =  binary_search(data, choice)
    print 'Found it at index: ' + str(index)
    assert data[index] == choice

for x in xrange(1000):
    test_binary_search()

Answer 1

请参阅标准库中Python的bisect模块的源代码，以查看用于二进制搜索和在该语言中使用的二进制插入的公认实现：

"""Bisection algorithms."""

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

insort = insort_right   # backward compatibility

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

bisect = bisect_right   # backward compatibility

def insort_left(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

# Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass

关于您的代码，让我们看看可以进行哪些改进：

def binary_search(alist, item):
    first = 0
    last = len(alist)-1
    found = False
    midpoint = None
    while True:
        midpoint = first + ((last-first) // 2)
        if alist[midpoint] == item:
            return midpoint
        elif alist[midpoint] < item:
            first = midpoint
        elif alist[midpoint] > item:
            last = midpoint

found和midpoint的初始值从未使用过，因此可以删除：

def binary_search(alist, item):
    first = 0
    last = len(alist)-1
    while True:
        midpoint = first + ((last-first) // 2)
        if alist[midpoint] == item:
            return midpoint
        elif alist[midpoint] < item:
            first = midpoint
        elif alist[midpoint] > item:
            last = midpoint

我的测试是用Python3.5执行的，所以代码看起来可能有点奇怪。当寻找不存在的东西时会发生什么？

def binary_search(alist, item):
    first = 0
    last = len(alist)-1
    while True:
        midpoint = first + ((last-first) // 2)
        if alist[midpoint] == item:
            return midpoint
        elif alist[midpoint] < item:
            first = midpoint
        elif alist[midpoint] > item:
            last = midpoint

alist = list(range(10, 20))
item = 9
print(binary_search(alist, item))

如果该值太小，则该函数进入无限循环。那么当这个值太大时呢？

def binary_search(alist, item):
    first = 0
    last = len(alist)-1
    while True:
        midpoint = first + ((last-first) // 2)
        if alist[midpoint] == item:
            return midpoint
        elif alist[midpoint] < item:
            first = midpoint
        elif alist[midpoint] > item:
            last = midpoint

alist = list(range(10, 20))
item = 10
print(binary_search(alist, item))

程序输出零。这也不对。下面是您的代码的重写，希望能够纠正这个问题：

import random


def main():
    for _ in range(1000):
        array = sorted(random.sample(range(10000), 9000))
        value = random.randrange(10000)
        index = binary_search(array, value)
        if index is None:
            assert value not in array
        else:
            assert array[index] == value


def binary_search(array, value):
    start, stop = 0, len(array)
    while start < stop:
        offset = start + stop >> 1
        sample = array[offset]
        if sample < value:
            start = offset + 1
        elif sample > value:
            stop = offset
        else:
            return offset

if __name__ == '__main__':
    main()