查找
-
查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程
-
列表查找（线性表查找）：从列表中查找指定元素
- 输入：列表、待查找元素
- 输出：元素下标（未找到元素时一般返回None或-1）
-
内置列表查找函数：index()
顺序查找(Linear Search)
-
顺序查找：也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止
-
时间复杂度：O(n)
def linear_search(li,val):
for ind ,v in emumerate(li):
if v == val:
return ind
else:
return None
#或者
def linear_search(data_set,value):
for i in range(range(data_set)):
if data_set[i] == value:
return i
return 二分查找(Binar Search)
-
二分查找：又叫折半查找，从有序列表的初始候选区 li[0:n] 开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半
def binary_search(li,val): # val：元素
left = 0
right = len(li) - 1
while left <= right: # 候选区有值
mid = (left + right)// 2
if li[mid] == val:
return mid
elif li[mid] > val: # 带查找的值在mid左侧
right = mid -1
else: # li[mid] < val 带查找的值在mid右侧
left = mid + 1
else:
return None-
时间复杂度：O(logn)
测试运行时间代码：
import time
def cal_time(func):
def wrapper(*args,**kwargs):
t1 = time.time()
result = func(*args,**kwargs)
t2 = time.time()
print("%s running time: %s secs." % (func.__name__,t2-t1))
return result
return wrapper
# 运用时，先导入这个模块，再用@cal_time语句放在函数代码，如：
@cal_time
def binary_search(li,val): # val：元素
left = 0
right = len(li) - 1
while left <= right: # 候选区有值
mid = (left + right)// 2
if li[mid] == val:
return midcal_time
elif li[mid] > val: # 带查找的值在mid左侧
right = mid -1
else: # li[mid] < val 带查找的值在mid右侧
left = mid + 1
else:
return None注：内置函数 index() 用的是线性查找。
