来自图解LeetCode初级算法的笔记(分块查找没有研究)
为什么要查找
查找是搜索算法,可用在判断一个数是否在该数列种,或者找出一个无序数列中该数列的位置
顺序查找
就是将数列从头到尾的查找一遍
for i in rang(array):
if array[i]==key:
return i
return -1
二分法查找
直接找数列中间的那个数字与被查找数(key)相比。如果这个数比key小,在就在这个有序数列的前面,否则就是这个然,要不然就在这个数的后面。相应的知道了范围,我们就可以在那个范围中去查找。
这里的关键在于如何确定,那一部分索引的中间元素,这里先引入索引0,和最后一个索引,先求出中间的索引,然后判断是在前的话,就把中间索引复制给right,然后继续求中间索引,这样不有可能会求不到么。不会,因为是有序的。
left = 0
right = iLen -1
# 重新循环遍历,left,rignt重新赋值;这样来确定一半索引处的位置么;一个部分中的中间元素
while right - left > 1:
mid = (left + right) // 2 # 一半索引处
if key < iList[mid]:
right = mid # 一半索引值给了right
elif key > iList[mid]:
left = mid # 一半索引值给了left
else:
return mid # 跳出循环体所在的方法,相当于跳出循环体。
斐波那契查找
又称黄金分隔数列,指的是该数列中相邻两个数的壁纸越趋向于黄金比例值。相较于二分查找来说,它的分隔点是0.618,假如一个数列中有1000个数,二分查找法查找的位置在索引500这,而斐波那契查找则在618这。
斐波那契查找的索引是按照斐波那契数的排列,比如数列长10,则找一个比他大的斐波那契数13,找13之前的斐波那契数8,找这个索引。然后不断循环,直至找到那个书。这里就需要用到斐波那契数列的构建,也就是递归了。
斐波那契数的列表相加生成
def fibonacci(n):
'''return the last element of the fibonacci sequence'''
fList = [1, 1]
while n > 1 :
fList.append(fList[-1] + fList[-2])
n -= 1
print(fList)
return fList[-1]
接着是fibonacci查找关键代码
k = 1
while fibonacci(k) -1 < iLen - 1: #fibonacci数列中的最后一个元素要比iList的长度稍微大一点
k += 1
while right - left > 1:
mid = left + fibonacci(k - 1) # fibonacci数列中的最后一个元素前面的那个数
if key < iList[mid] :
right = mid - 1 # 在左边,则中间索引减少一
k -= 1 # 斐波那契数是前面一个元素
elif key == iList[mid]:
return mid
else:
left = mid + 1 # 在右边的话,中间索引加1,并且赋值给左边
k -= 2 # k-2没搞懂,为啥减少2呢
插值查找
fibonacci查找和二分查找的区别在于查找数列中选取比较点(参照点)。而插值查找则给出了一个大多数情况下的理论上最科学的比较点
mid = left +(key-iList[left])*(right-left)//(iList[right]-iList[left]) # 那为什么这个点是查找的最优点呢
插值查找关键代码
while right - left > 1:
mid = left + (key - iList[left]) * (right - left) // (iList[right] - iList[left])
if mid == left:
mid += 1 #当iList[right]和iList[left]相差太大时,有可能导致mid一直都等于left,从而陷入死循环
if key < iList[mid]:
right = mid
elif key > iList[mid]:
left = mid
else:
return mid
if key == iList[left]:
return left
elif key == iList[right]:
return right
else:
return -1
分块查找
分块查找与以上的查找方式不同,顺序查找的数列可以是无序的,二分查找和斐波那契查找数列必须是有序的,分块查找介于两者之间,需要块有序,元素可以无序。插值查找也是有序查找
原理:
按照一定的取值范围将数列分成数块,块内的元素可以是无序,单块必须有序
块有序:处于后面位置的块中的最小元素都要比前面位置块中的最大元素大
第一次查找是将被查找数key与块的分界数相比较,确定key属于哪个块
第二次查找
块内的查找就是顺序查找
分块操作(没研究)
iList = randomList(20)
indexList = [[250, 0], [500, 0], [750, 0], [1000, 0]]
def divideBlock():
global iList, indexList
sortList = []
for key in indexList: # 分块操作
subList = [i for i in iList if i < key[0]] #列表推导, 小于key[0]的单独分块
key[1] = len(subList)
sortList += subList # 加入到新建的列表中
iList = list(set(iList) - set(subList)) #过滤掉已经加入到subList中的元素
iList = sortList
print()
return indexList
在块中进行查找
def blockSearch(iList, key, indexList):
print("iList = %s" %str(iList))
print("indexList = %s" %str(indexList))
print("Find The number : %d" %key)
left = 0 #搜索数列的起始点索引
right = 0 #搜索数列的终点索引
for indexInfo in indexList:
left += right
right += indexInfo[1]
if key < indexInfo[0]:
break
for i in range(left, right):
if key == iList[i]:
return i
return -1