题目

看一下这道编程题。

使用python对已排序的list中的元素进行二分查找，如果找到返回True，否则返回False，并编写unittest单元测试用例来进行验证。

二分查找的算法复杂度比直接遍历列表中元素进行查找的复杂度要低，具体是多少大家可以去看一下。

二分查找是这样工作的。

• 首先找到列表中排在中间的元素，比较目标元素与该元素的大小，如果中间的元素等于目标元素，则返回True，否则返回False
• 如果目标元素比该元素大，则在中间元素与最后一个元素之间重复步骤1
• 如果目标元素比该元素小，则在中间元素与第一个元素之间重复步骤1

拿下面一组数组为例。

[1, 2, 3, 4, 5, 6, 7, 8, 9]，假设我们需要查找7。那么我们的步骤是

• 先找到[1, 2, 3, 4, 5, 6, 7, 8, 9]的中间数字5
• 7 > 5，于是在[6, 7, 8, 9]中进行二分查找
• [6, 7, 8, 9]的中间数字是8
• 7 < 8 于是在[6, 7]也就是左半边二分查找
• [6, 7]的中间元素是7，等于目标元素，于是找到，返回True

可以看到我们只查找了3次就找到了7，如果是遍历的化，我们需要遍历6次，也就是1到6，二分的优势是很明显的。

参考答案

import unittest

def bin_search(arr, target):
    length = len(arr)
    mid = length / 2 # 找到中间元素

    if arr[mid] == target: # 如果该元素等于目标元素
        return True

    if length == 1 and arr[0] != target: # 目标元素不存在
        return False

    if target > arr[mid]: # 如果目标元素大于中间元素
        return bin_search(arr[mid+1:], target) # 在列表的右半边递归进行二分查找
    else: # 小于的情况
        return bin_search(arr[:mid], target) # 在列表的左半边递归进行二分查找


class BinSearchTestCase(unittest.TestCase):

    def test_bin_search(self):
        test_data = [9, 5, 2, 7] # 测试数据
        test_data.sort() # 先排序

        self.assertEqual(bin_search(test_data, 2), True)
        self.assertEqual(bin_search(test_data, 9), True)
        self.assertEqual(bin_search(test_data, 1), False)
        self.assertEqual(bin_search(test_data, 999), False)


if __name__ == '__main__':
    unittest.main()

思考

这里我们使用了递归的方式实现了二分查找，使用递归的好处是逻辑相对简单直观，当然我们也可以使用循环的方式来实现相同的功能。