有序列表的顺序搜索
二分查找
# 二分搜索
sou=[17,18,22,28,38,78,89,99,100]
def binarysearch(list,item):
first=0
last=len(list)-1
while first<=last:
minpoint=(first+last)//2
#print(minpoint,list[minpoint])
if list[minpoint]==item:
return minpoint
else:
if list[minpoint]>item:
last=minpoint-1
else:
first=minpoint+1
return -1
print(binarysearch(sou,17))
print(binarysearch(sou,11))
输出:
4 38
1 18
0 17
0
4 38
1 18
0 17
-1
哈希hash
欧拉筛法
# 欧拉筛
# n,q=list(map(int,input().split()))
n=int(input())
max=n
result=[]
panduan=[1]*max
for i in range(2,max):
if panduan[i]:
result.append(i)
for e in result:
if e*i>=max:
break
panduan[e*i]=0
if i%e==0:
break
print(len(result))
# for i in range(q):
# print(result[int(input())-1])
print(result)
12
5
[2, 3, 5, 7, 11]