第四讲 搜索与排序(2)——二分搜索

代码1——递归式

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)

2. 测试部分

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. 分析
   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——循环式

1. 主体部分

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

2. 测试部分
   同上
3. 两种方式的对比
   3.1 边界条件。循环式通过while来控制，边界条件是l <= h，该条件与递归式的边界条件l > h互补，前者是保持循环的条件，后者是停止递归的条件。
   3.2 初始状态。循环式在循环之前设置好初始状态，递归式把初始状态当做参数传入递归函数。
   3.3 终止。循环式跳出循环后终止，递归式满足边界条件时终止。