二分查找(Binary Search)

Last Updated: 2023-10-11 01:34:16 Wednesday

-- TOC --

出了道题给自己:用loop和recursive这两种方式,分别实现binary search,比较性能。

二分查找,Binary Search,是常用的性能很高的查找算法,Big-Oh为\(O(\log{N})\),但它必须在已经排好序的元素序列中执行。插入排序的实现,插入部分就可基于二分查找来提高性能。参考:常用内部排序算法的C语言实现

Binary Search的Python实现和测试,代码如下:

def bsearch_loop(x: int, lst: list[int]) -> int:
    """ binary search, loop version """
    if (s:=len(lst)) == 0:
        return -1  # not found
    left = 0
    right = s-1
    while left <= right:
        m = (right+left) // 2
        if lst[m] == x:
            return m
        if lst[m] < x:
            left = m + 1
        else:
            right = m - 1
    return -1


def bsearch_recur(x: int, lst: list[int]) -> int:
    """ binary search, recursive version """
    if (s:=len(lst)) == 0:
        return -1  # not found
    m = s // 2
    if lst[m] == x:
        return m
    if lst[m] < x:
        j = bsearch_recur(x, lst[m+1:])
        return -1 if j==-1 else m+j+1
    else:
        return bsearch_recur(x, lst[:m])


for i in range(1000):
    assert bsearch_loop(i,list(range(1000))) == i
    assert bsearch_recur(i,list(range(1000))) == i
for i in range(-1000,0):
    assert bsearch_loop(i,list(range(1000))) == -1
    assert bsearch_recur(i,list(range(1000))) == -1
for i in range(1000,2000):
    assert bsearch_loop(i,list(range(1000))) == -1
    assert bsearch_recur(i,list(range(1000))) == -1


import time
from timeit import timeit


n = int(1e6)
print('bsearch_loop:',
      timeit('bsearch_loop(0,lst)',
             setup='lst=list(range(1000))',
             timer=time.process_time,
             number=n,
             globals=globals())/n)
print('bsearch_recur:',
      timeit('bsearch_recur(0,lst)',
             setup='lst=list(range(1000))',
             timer=time.process_time,
             number=n,
             globals=globals())/n)

输出:

bsearch_loop: 1.8980469e-06
bsearch_recur: 6.323083636e-06

总结:

思考:

Binary Search的应用存在局限:

补充:

Python标准库中的bisect模块

本文链接:https://cs.pynote.net/ag/202307051/

-- EOF --

-- MORE --