11_线性查找和二分查找

线性查找

if __name__ == '__main__':

    number_list = [0, 1, 2, 3, 4, 5, 6, 7]

    def linear_search(value, iterable):
        for index,val in enumerate(iterable):
            if val == value:
                return index
        return -1
    assert linear_search(5, number_list) == 5

    def linear_search_v2(predicate, iterable):
        for index, val in enumerate(iterable):
            if predicate(val): #传入lamda表达式
                return index
        return -1
    assert linear_search_v2(lambda x: x == 5, number_list) == 5

    def linear_search_recusive(array, value):
        if len(array) == 0:
            return -1
        # 从后往前匹配
        index = len(array) - 1
        if array[index] == value:
            return index
        return linear_search_recusive(array[0:index], value)
    assert linear_search_recusive(number_list, 5) == 5
    assert linear_search_recusive(number_list, 8) == -1
    assert linear_search_recusive(number_list, 7) == 7
    assert linear_search_recusive(number_list, 0) == 0

二分查找

    def binary_search_recursive(sorted_array, beg, end, val):
        # beg 开始查找的区间 左闭右开
        # end 结束位置
        if beg >= end:
            return -1
        mid = int((beg + end) / 2)
        if sorted_array[mid] == val:
            return mid
        elif sorted_array[mid] > val:
            return binary_search_recursive(sorted_array, beg, mid, val)
        else:
            return binary_search_recursive(sorted_array, mid + 1, end, val)

    def test_binary_search_recursive():
        a = list(range(10))
        for i in a:
            assert binary_search_recursive(a, 0, len(a), i) == -1
        assert binary_search_recursive(a, 0, len(a), -1) == -1
        assert binary_search_recursive(a, 0, len(a), 10) == -1