8.1常用的查找算法
我们常用的查找有四种:
1)顺序(线性)查找
2)二分查找/折半查找
3)插值查找
4)斐波那契查找
8.2线性查找算法介绍：
有一个数列：{1,8,10,89,1000,1234}，判断数列中是否包含此名称【顺序查找】要求:如果找到了，就提示找到，并给出下标值。
8.3二分查找算法介绍
8.3.1二分查找：
请对一个有序数组进行二分查找{1,8,10,89,1000,1234}，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。
8.3.2二分查找算法的思路
8.3.3二分查找的代码
#一位数组二分查找升级版：查找出所有相同的数字的下标
#使用二分查找，要求数字有序，从小到大或从大到小皆可，但代码有细微差别
def BinarySearch(list,left,right,findnumber):
#list 查找的列表
#left 左索引
#right 右索引
#findnumber 要找的数
mid = (left+right)//2
if left > right:
print("none")
return 0
if findnumber < list[mid]:
BinarySearch(list,left,mid-1,findnumber)
# 这边直接用left，mid-1 因为如果查找完右边再进行左边的查找的话 此时第二次left将不为0 而是第一次查找的left，但同时在进行第一次的右查找的时候，此时的left是第0次的mid
#反推过来，第0次的mid 作为第一次右查找的left值，第二次的左查找的left为原先的left，因此这里只需要将left传给第二次的左查找即可，
#[1,3,5,7,9,11,13,15,17,19]可以根据这个列表去找11 或者12 进行 模拟
# 而这边用mid-1 是因为 mid肯定不是我们要找的值了，下边的elif 类似
elif findnumber > list[mid]:
BinarySearch(list,mid+1,right,findnumber)
elif findnumber == list[mid]:
templeft = mid-1
tempright = mid+1
templist = [-1 for i in range(len(list))]
templist[mid] = mid
#此时mid对应的值就是我们要找的值了，找到mid的话要继续找还有没有一样的值，但是不确定mid左边右边还是不是要找的值，因此对mid左边右边都要进行比对。
while((right > tempright) and (list[tempright] == findnumber)):
templist[tempright] = tempright
#这里是将templist每个元素置为-1，如果发现找到值了，那么对应下标的值改为对应值，再顺序输出所有不是-1的值即可得到所有相同值的下标。
tempright = tempright+1
while((left < templeft) and (list[templeft] == findnumber)):
templist[templeft] = templeft
templeft = templeft -1
for i in range(len(templist)):
if templist[i] != -1:
print(templist[I])
findlist = [1,3,5,7,9,11,11,11,11,11,11,11,13,15,17,19]
BinarySearch(findlist,0,len(findlist),11)
8.4插值查找算法
1)插值查找原理介绍:插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
2)将折半查找中的求mid索引的公式,low表示左边索引left,high表示右边索引right.key就是前面我们讲的findVal
3)intmid=low+(high-low)(key-arr[low])/(arr[high]-arr[low]);/插值索引/对应前面的代码公式：intmid=left+(right–left)(findVal–arr[left])/(arr[right]–arr[left])
8.4.1插值查找算法代码：
#插值查找（按比例查找）
def BinarySearch(list,left,right,findnumber):
#list 查找的列表
#left 左索引
#right 右索引
#findnumber 要找的数
mid = left + int(((findnumber - list[left])//(list[right] - list[left]))*(right-left))
#int(((findnumber - list[left])//(list[right] - list[left])) 这个其实就是一个比值，与1/2 类似
#与 二分查找的唯一区别
if left > right:
print("none")
return 0
if findnumber < list[mid]:
BinarySearch(list,left,mid-1,findnumber)
elif findnumber > list[mid]:
BinarySearch(list,mid+1,right,findnumber)
elif findnumber == list[mid]:
templeft = mid-1
tempright = mid+1
templist = [-1 for i in range(len(list))]
templist[mid] = mid
while((right > tempright) and (list[tempright] == findnumber)):
templist[tempright] = tempright
tempright = tempright+1
while((left < templeft) and (list[templeft] == findnumber)):
templist[templeft] = templeft
templeft = templeft -1
for i in range(len(templist)):
if templist[i] != -1:
print(templist[I])
findlist = [1,3,5,7,9,11,11,11,11,11,11,11,13,15,17,19]
BinarySearch(findlist,0,len(findlist)-1,11)
8.4.2插值查找注意事项：
1)对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找,速度较快.
2)关键字分布不均匀的情况下，该方法不一定比折半查找要好
8.5斐波那契(黄金分割法)查找算法
8.5.1斐波那契(黄金分割法)查找基本介绍:
1)黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
2)斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618
8.5.2斐波那契(黄金分割法)原理:
斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示:
对F(k-1)-1的理解：1)由斐波那契数列F[k]=F[k-1]+F[k-2]的性质，可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1。该式说明：只要顺序表的长度为F[k]-1（F[k]代表这是个斐波那契数列的数字如13，-1是因为符合数组从0开始，也就是下标为12），则可以将该表分成长度为F[k-1]-1和F[k-2]-1（如13可以分成8和5也就是下标为7和4）的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1（mid= 0 + 8 -1 = 7也就是下标为7的位置就是这个mid位置）
2)类似的，每一子段也可以用相同的方式分割
3)但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。while(n>fib(k)-1)k++;
8.5.3斐波那契查找代码实现：
#斐波那契查找
def fibonacci(num):
#生成斐波那契数列的列表
fiblist = []
if num == 1:
fiblist.append(1)
elif num == 2:
fiblist.append(1)
fiblist.append(1)
else:
fiblist.append(1)
fiblist.append(1)
for i in range(num-2):
fiblist.append(fiblist[i]+fiblist[i+1])
return fiblist
def fibonacciSearch(searchlist,findValue,maxfibnum):
fiblist = fibonacci(maxfibnum)
for i in range(maxfibnum):
#这个for循环是用于夸张searchlist的个数与斐波那契数列某一个值匹配，这样才可以对这个searchlist进行切分，分成 f[k]=f[k-1]+f[k-2] f[k]即斐波那契数列的某一项
if fiblist[i] >= len(searchlist):
for j in range(fiblist[i]- len(searchlist)):
searchlist.append(searchlist[len(searchlist)-1])
break
low = 0
high = len(searchlist)
while(low < high):
#这里只需要满足low < high即可，因为当low==high的时候，如下所示，查找8的时候，再倒数第二次查找的时候，mid为9，此时还没找到，说明这个数不是9
#再因为最后一次low 为 8 high 为9 ，首先9不是要找的数，而如果8还不是的话，那么意味着这个数应该介意8与9之间（这里是将第八个数当成8第九个数当成9了）
#如果不这么当的话比如 第八个数是80 ，第九个数是90 要找的数是85这样更好理解， 那么此时 应该是符合findValue > searchlist[mid]，那么此时
#low = mid+1 low为 9 ，那么就不满足low < high 因此就没找到了。
mid = low + fiblist[i-1] -1
print("low",low)
print("high",high)
print("mid",mid)
if (findValue < searchlist[mid]):
i = i-1
high = mid
elif (findValue > searchlist[mid]):
i = i -2
low = mid+1
elif (findValue == searchlist[mid]):
print(mid)
return
print("not found")
return
searchlist = [0,1,2,3,4,5,6,7,8,9,10,11]
fibonacciSearch(searchlist,8.6,20)
