Last Updated: 2024-02-05 11:28:52 Monday
-- TOC --
出了道题给自己：用loop和recursive这两种方式，分别实现binary search，比较性能。
二分查找，Binary Search，是常用的性能很高的查找算法，时间复杂度为\(\Theta(\log_2{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
总结：
(left+right)//2和length//s。//2和>>1性能一样，怎么写都行，不用纠结。linear recursive。（另一种叫做tree recursive或multi-recrusive，典型如merge sort，并归排序）思考：
Binary Search的应用存在局限：
补充：
本文链接：https://cs.pynote.net/ag/202307051/
-- EOF --
-- MORE --