python算法与数据结构（14）线性查找和二分查找

线性查找：

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

def test_linear_search():
    assert linear_search(5, number_list) == 5

传一个谓词进去，传入一个函数进去。

"""传入一个函数"""

number_list = [0, 1, 2, 3, 4, 5, 6, 7]
def linear_search_v2(predicate, iterable):
    for index, val in enumerate(iterable):
        if predicate(val):
            return index
    return -1


def test_linear_search_ve():
    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)

def test_linear_search_recusive():
    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(sorted_array, val):
    if not sorted_array:
        return -1
    beg = 0
    end = len(sorted_array) - 1
    while beg <= end:
        mid = int((beg+end) / 2)
        if sorted_array[mid] == val:
            return val
        elif sorted_array[mid] > val:
            end = mid - 1
        else:
            beg = mid + 1
    return -1

def test_binary_search():
    a = list(range(10))

    # 正常值
    assert binary_search(a, 1) == 1
    assert binary_search(a, -1) == -1
    # 异常值
    assert binary_search(None, 1) == -1
    # 边界值
    assert binary_search(a, 0) == 0

递归查找二分法

"""递归二分查找"""
def digui_binary(sorted_array, val):
    n = len(sorted_array)
    if n < 1:
        return -1
    mid = n // 2
    if sorted_array[mid] == val:
        return True
    elif sorted_array[mid] > val:
        return digui_binary(sorted_array[0:mid], val)
    else:
        return digui_binary(sorted_array[mid+1:n], val)