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