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]

相关推荐