代码1——递归式
- 主体部分
def bi_search_re(num_list, val):
def bi_search(l, h):
if l > h:
return -1
mid = (l + h) // 2
if num_list[mid] == val:
return mid
elif num_list[mid] < val:
return bi_search(mid+1, h)
else:
return bi_search(l, mid-1)
return bi_search(0, len(num_list)-1)
- 测试部分
import unittest
class MyTest(unittest.TestCase):
def setUp(self) -> None:
self._f = bi_search_re
def test0(self):
data = []
r = self._f(data, 1)
self.assertEqual(-1, r)
def test1(self):
data = [1]
r = self._f(data, 1)
self.assertEqual(0, r)
r = self._f(data, 2)
self.assertEqual(-1, r)
def test2(self):
data = [1, 2, 3, 5, 7, 8, 9]
r = self._f(data, 7)
self.assertEqual(4, r)
r = self._f(data, 6)
self.assertEqual(-1, r)
- 分析
3.1 mid = (l + h) // 2
换成mid = (l + h + 1) // 2
也可以
3.2 代码中是先右向判断再左向判断,也可以调换顺序
3.3 边界条件是if l > h:return -1
,即不再继续递归的条件
if num_list[mid] == val:
return mid
elif num_list[mid] > val:
return bi_search(l, mid-1)
else:
return bi_search(mid+1, h)
代码2——循环式
- 主体部分
def bi_search_iter(num_list, val):
l, h = 0, len(num_list)-1
while l <= h:
mid = (l + h) // 2
if val > num_list[mid]:
l = mid + 1
elif val < num_list[mid]:
h = mid - 1
else:
return mid
return -1
- 测试部分
同上
- 两种方式的对比
3.1 边界条件。循环式通过while来控制,边界条件是l <= h
,该条件与递归式的边界条件l > h
互补,前者是保持循环的条件,后者是停止递归的条件。
3.2 初始状态。循环式在循环之前设置好初始状态,递归式把初始状态当做参数传入递归函数。
3.3 终止。循环式跳出循环后终止,递归式满足边界条件时终止。
网友评论