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]