9 二分查找

题目

考二分查找法的

binary_search.py

#!/bin/env python3
# -*- coding: utf-8 -*-
# version: Python3.X


__author__ = '__L1n__w@tch'


def binary_search(a_list, number_to_find):
    """
    二分查找法
    :param a_list: 待查找列表
    :param number_to_find: 待查找数字
    :return: int() or False
    """
    start, end = 0, len(a_list) - 1
    while start < end:
        middle = (start + end) // 2
        if a_list[middle] > number_to_find:
            end = middle
        elif a_list[middle] < number_to_find:
            start = middle + 1
        else:
            return middle
    return start if a_list[start] == number_to_find else False


if __name__ == "__main__":
    List = [i for i in range(10)]
    print(binary_search(List, 2))

单元测试

#!/bin/env python3
# -*- coding: utf-8 -*-
# version: Python3.X
""" 单元测试二分查找
"""
import random
import unittest
from binary_search import binary_search


__author__ = '__L1n__w@tch'


class TestBinarySearch(unittest.TestCase):
    def test(self):
        list_wait_to_search = sorted([random.randint(-1000, 1000) for i in range(100)])
        number_wait_to_search = list_wait_to_search[random.randint(0, 100)]

        self.failUnless(number_wait_to_search ==
                        list_wait_to_search[binary_search(list_wait_to_search, number_wait_to_search)])