python算法之查找
#顺序查找#基本思想:从第一个元素到最后一个元素依次查找def sqsearch(numList, x): for id,num in enumerate(numList): if num == x: return id return str(x) + ‘ is not exist!‘print(sqsearch([1,2,4,5,6,8,12,24,32,44], 5))#二分查找(折半查找)#基本思想:将n个数组成的有序数列分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,# 如果x=a[n/2]则找到x,算法终止;如果x<a[n/2],则只要在数组a的左半部继续搜索x;# 如果x>a[n/2],则只要在数组a的右半部继续搜索xdef binarysearch(numList, x): low = 0 high = len(numList) - 1 while low <= high: mid = (low + high) / 2 if x == numList[mid]: return mid if x > numList[mid]: low =mid + 1 if x < numList[mid]: high = mid - 1 return str(x) + " is not exist!"print(binarysearch([1,2,4,5,6,8,12,24,32,44], 5))#插入查找(按比例查找)#基本思想:属于二分查找的改进方法,不同之处是将折半的取法变为按比例def insertsearch(numList, x): low = 0 high = len(numList) - 1 while low <= high: mid = low + (x-numList[low])/(numList[high]-numList[low])*(high-low)#插入查找公式 if x == numList[mid]: return mid if x > numList[mid]: low = mid + 1 if x < numList[mid]: high = mid - 1 return str(x) + " is not exist!"print(insertsearch([1, 2, 4, 5, 6, 8, 12, 24, 32, 44], 5))#斐波那契查找(黄金比例查找)#基本思想:属于二分查找的改进方法,不同之处是将折半的取法变为0.618:1的取法(以列表的元素个数用斐波那契数列来近似)def fib(x): if x==1 or x==2: return 1 else: return fib(x-1) + fib(x-2)def find(key): x=1 fibnum = [] while fib(x)<key: fibnum.append(fib(x)) x +=1 fibnum.append(fib(x)) return fibnumdef fibsearch(numList, x): org=orgleng = len(numList) #若原始列表长度不足斐波那契数,则用列表最后一个数补,直到长度等于斐波那契数(注:只需要补1次就行) fibnum = find(orgleng) while orgleng < fibnum[-1]: numList.append(numList[-1]) orgleng += 1 k = len(fibnum) low = 0 high = len(numList) - 1 while low <= high: mid = low + fib(k-1)-1#按照斐波那契数列取值划分 print(str(numList[low:mid]) + ‘ ‘ + str(numList[mid:high+1])) if x > numList[mid]: low = mid + 1 k -= 2 #当x处于后半段时 elif x < numList[mid]: high = mid - 1 k -= 1 #当x处于前半段时 else: #若mid小于原始列表最大索引,则返回;若mid大于原始列表最大索引,则返回原始列表最大索引 if mid < org: return mid else: return org - 1 return str(x) + " is not exist!"print(fibsearch([1, 2, 4, 5, 6, 8, 12, 24, 32, 44],2))# [1, 2, 4, 5, 6, 8, 12] [24, 32, 44, 44, 44, 44]# [1, 2, 4, 5] [6, 8, 12]# [1, 2] [4, 5]# [1] [2]
相关推荐
赶路人儿 2020-11-02
scuyxi 2020-10-25
csdnfelix 2020-10-18
代码之神 2020-10-15
Pokemogo 2020-09-17
MasterCui 2020-09-08
Morelia 2020-09-04
meylovezn 2020-08-30
Hannah 2020-08-19
hugebawu 2020-08-17
scuyxi 2020-08-16
hang0 2020-08-16
higher0 2020-08-11
Tips 2020-08-08
Tristahong 2020-08-05
xiesheng 2020-08-02
huakai 2020-07-26
RememberMePlease 2020-06-26
zangdaiyang 2020-06-25