欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python-线性查找与二分查找

程序员文章站 2022-03-14 20:44:03
...

线性查找

线性查找就是从头到尾,直到符合条件了就返回。比如在一个list中找到一个等于5的元素并返回下标:

number_list = [0,1,2,3,4,5,6,7]
'''
    enumerate()函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,
    同时列出数据和数据下标,一般用在 for 循环当中。
'''
#enumerate()用法实例
>>>seasons = ['Spring','Summer','Fall','Winter']
>>>list(enumerate(seasons))
[(0,'Spring'),(1,'Summer'),(2,'Fall'),(3,'Winter')]
>>>list(enumerate(seasons,start=1))     #下标从1开始
[(1,'Spring'),(2,'Summer'),(3,'Fall'),(4,'Winter')]

#for 循环中使用enumerate
>>>seq = ['one','two','three']
>>>for i,element in enumerate(seq):
...     print i, element
...
0 one
1 two
2 three


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

当然我们需要来一点花样,比如传一个谓词进去,你要知道,在python里一切 皆对象,所以我们可以把函数当成一个参数传给另一个函数

def linear_search_v2(predicate,iterable):
    for index,val in enumerate(iterable):
        if predicate(val):
            return index
    return -1

assert linear_search_v2(lambda x: x==5, number_list) == 5

尝试用递归来实现线性查找

number_list = [0,1,2,3,4,5,6,7]
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

二分查找

线性查找针对的是无序序列,假如一个序列已经有序了呢,我们还需要
从头找到尾吗?当然不用,折半(二分)是一种经典思想。日常生活中还有
哪些经典的二分思想呢?

1.猜数字游戏
2.一尺之棰,日取其半,万世不竭
3.有些民间股神,告诉一堆人某个股票会涨,告诉另一半人会跌。
后来真涨了,慢慢又告诉信了他的一半人另一个股票会涨,另一半说
会跌。就这样次数多了总有一些人信奉他为股神...
def binary_search(sorted_array,val):
    if not sorted_array:
        return -1

    beg = 0
    end = len(sorted_array) - 1

    while beg <= end:
        #beg + (end-beg)/2,为了屏蔽python 2/3 差异用了强转
        mid = int((beg + end) / 2)
        if sorted_array[mid] == val:
            return mid
        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