查找算法-Python
无序表查找
线性查找 O( n )
适用于线性表的顺序存储结构和链式存储结构。
#无序数列遍历查找
def unordered_search(lis,key):
for i in range(len(lis)):
if lis[i] == key:
return i
return False
assert unordered_search([1,2,3,2,1,4,5],6)==False
assert unordered_search([1,2,3,2,1,4,5],3)==2
有序表查找
二分查找 Binary Search O( log(n) )
对半分割数列
#递增数列二分查找
def binary_search(lis, key):
l, h = 0, len(lis) - 1
while l <= h:
mid = (l + h)//2
if lis[mid] == key:
return mid
elif lis[mid] > key:
h = mid - 1
elif lis[mid] < key:
l = mid + 1
return False
assert binary_search([1,2,3,2,1,4,5],6)==False
assert binary_search([1,2,3,2,1,4,5],4)==5
复杂度分析
- 时间复杂度：折半搜索每次把搜索区域减少一半，时间复杂度为 O(logn)
- 空间复杂度：O(1)
插值查找 O( log(n) )
按差值比例分割数列
对二分查找的优化，让问题规模更快的缩减
value =low + int( (high - low) * (key - list[low]) / (list[high] - list[low]) )
用此 value 成比例代替二分查找中的中间值。
但是当 key 值过大， value 有可能会超出列表范围。需要额外判定。
# 递 增数列插值查找
def interpolation(lis, key):
l, h = 0, len(lis) - 1
while l <= h:
mid = l + int((h - l) * (key - lis[l]) / (lis[h] - lis[l]))
# print(f'l {l}; h {h}; mid {mid}')
if mid > len(lis) - 1:
return False
if lis[mid] == key:
return mid
elif lis[mid] > key:
h = mid - 1
elif lis[mid] < key:
l = mid + 1
return False
assert interpolation([1,2,3,2,1,4,5],6)==False
assert interpolation([1,2,3,2,1,4,5],4)==5
插值查找算法复杂度与二分法一致，也属于O(log(n))级别的。
其优点是，对于表内数据量较大，且关键字分布比较均匀的查找表，使用插值算法的平均性能比二分查找要好得多。
反之，对于分布极端不均匀的数据，则不适合使用插值算法。
复杂度分析
- 时间复杂性：如果元素均匀分布，则O（log log n）），在最坏的情况下可能需要 O（n）。
- 空间复杂度：O（1）。
斐波那契查找 O( log(2n) )
使用斐波那契数列分割要查找的数列。
斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。
在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n](如果要补充元素，
则补充重复最后一个元素，直到满足F[n]个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，
后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
# 递增数列斐波那契查找
def fibonacci_search(lis, key):
fibo = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368]
l, h = 0, len(lis) - 1
k = 0
while h > fibo[k] - 1:
k += 1
i = h
while fibo[k] - 1 > i:
lis.append(lis[h])
i += 1
print(f'k---->{k}, fibo[k]---->{fibo[k]}, ')
print(lis)
while l <= h:
if k < 2:
mid = l
else:
mid = l + fibo[k-1] -1
print(f'low = {l}, high = {h}, mid = {mid}')
if key < lis[mid]:
h = mid - 1
k -= 1
elif key > lis[mid]:
l = mid + 1
k -= 2
else:
if mid <= h:
return mid
else:
return h
return False
assert fibonacci_search([1,2,3,2,1,4,5],6)==False
assert fibonacci_search([1,2,3,2,1,4,5,7,5,10,24,199],4)==5
#
复杂度分析
- 最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。
- 平均性能，要优于二分查找。但是在最坏情况下，比如这里如果key为1，则始终处于左侧半区查找，此时其效率要低于二分查找。
线性索引查找
索引按照结构可以分为：线性索引、树形索引和多级索引。
线性索引：将索引项的集合通过线性结构来组织，也叫索引表。
线性索引可分为：稠密索引、分块索引和倒排索引
稠密索引
在线性索引中，为数据集合中的每个记录都建立一个索引项。
稠密索引
给无序的集合，建立了一张有序的线性表。其索引项一定是按照关键码进行有序的排列。方法同上
分块索引 分块查找 O(log(m)+N/m)
给大量的无序数据集合进行分块处理，使得块内无序，块与块之间有序。
分块索引
将n个数据元素"按块有序"划分为m块（m ≤ n）。
每一块中的结点不必有序，但块与块之间必须"按块有序"；
即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
而第2块中任一元素又都必须小于第3块中的任一元素，……
流程
1、先选取各块中的最大关键字构成一个索引表；
2、查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
3、在已确定的块中用顺序法进行查找。
# 分块查找
def block_search(list, count, key):
length = len(list)
block_length = length//count
if count * block_length != length:
block_length += 1
print("block_length:", block_length) # 块的多少
for block_i in range(block_length):
block_list = []
for i in range(count):
if block_i*count + i >= length:
break
block_list.append(list[block_i*count + i])
result = binary_search(block_list, key)
if result != False:
return block_i*count + result
return False
数据量过大，建立完整的稠密索引耗时耗力，占用资源过多；但如果不做任何排序或者索引，那么遍历的查找也无法接受，只能折中，做一定程度的排序或索引。
分块索引的效率比遍历查找的O(n)要高一些，但与二分查找的O(logn)还是要差不少。O(log(m)+N/m)
倒排索引
不是由记录来确定属性值，而是由属性值来确定记录的位置，这种被称为倒排索引。其中记录号表存储具有相同次关键字的所有记录的地址或引用（可以是指向记录的指针或该记录的主关键字）。
倒排索引是最基础的搜索引擎索引技术。
散列表 哈希查找 Hash
哈希表以键-值(key-indexed) 存储数据，只要输入待查找的key，即可查找到其对应的值
流程：
1）用给定的哈希函数构造哈希表；
2）根据选择的冲突处理方法解决地址冲突；常见的解决冲突的方法：拉链法和线性探测法。
3）在哈希表的基础上执行哈希查找。
# 哈希查找
# 取余法构造哈希表
def myHash(data, hashLength):
return data % hashLength
# 哈希表检索数据
def searchHash(hash, hashLength, key):
hashAddress = myHash(key, hashLength)
#指定hashAddress存在，但并非关键值，则用开放寻址法解决
while hash.get(hashAddress) and hash[hashAddress] != key:
hashAddress += 1
hashAddress = hashAddress % hashLength
if hash.get(hashAddress) == None:
return False
return hashAddress - 1
# 数据插入哈希表
def insertHash(hash, hashLength, data):
hashAddress = myHash(data, hashLength)
# 解决冲突： key已经被占用时 开放寻址
while(hash.get(hashAddress)):
hashAddress += 1
hashAddress = myHash(hashAddress,hashLength)
hash[hashAddress] = data
def hash_search(lis,key):
hashLength = len(lis) + 1
hash = {}
for i in lis:
insertHash(hash,hashLength,i)
#print(hash)
return searchHash(hash, hashLength, key)
assert hash_search([1,2,3,2,1,4,5],6)==False
assert hash_search([1,2,3,2,1,4,5,7,5,10,24,199],4)==5
对于无冲突的Hash表而言，查找复杂度为O(1)（在查找前需要构建相应的Hash表）。
二叉查找树 BST 和平衡二叉树 AVL
多路查找树 B树
Reference
[1] 经典查找算法及其Python实现
[2] 七大查找算法（Python）
