常见的查找算法的原理及python实现

data=[1,3,4,5,6]
value=1
def linear_search(data,value):
flag=False
for i in range(0,len(data)):
if data[i]==value:
# return i
flag=True
print(‘找到了，在第%s个位置‘%i)
if not flag:
print(‘查找失败‘)
# linear_search(data,value)

#递归实现
def bin_search2(data,value):
mid=len(data)/2
if len(data)>1:
if value>data[mid]:
bin_search2(data[mid+1:],value)
elif value bin_search2(data[0:mid-1],value)
else:
return mid
else:
if data[0]==value:
return 0
else:
print(‘查找失败‘)

def bin_search(data,value):
flag=False
low=0
high=len(data)-1
while low<=high:
mid=(low+high)//2
if value>data[mid]:
low=mid+1
elif value high=mid-1
else:
flag=True
return mid
if not flag:
print(‘查找失败‘)
print(bin_search(data,value))

#练习
info=[
{"id":1001, "name":"张三", "age":20},
{"id":1002, "name":"李四", "age":25},
{"id":1004, "name":"王五", "age":23},
{"id":1007, "name":"赵六", "age":33}
]
def bin_search(data,value):
low=0
high=len(data)-1
while low<=high:
mid=(low+high)//2
if data[mid][‘id‘]==value:#取字典的value 用dic[key]
return (mid,data[mid])
elif data[mid][‘id‘] low=mid+1
else:
high=mid-1
else:
return (0,None)#根据返回值判断是否查到这个人
while True:
id=int(input(‘请输入需要查找的学号（退出请按Q）:‘).strip())
# print(type(id))
if id==‘q‘:
break
else:
num,info=bin_search(info,id)
if info==‘None‘:
print(‘查无此人‘)
else:
print(‘info:%s‘%info)