一 顺序查找
1 在列表中顺序查找特定的值key，如果找到返回该值在列表中的索引号，如果没有找到返回“不存在”
def sequential_search(lst, key): length = len(lst) for i in range(length): if lst[i] == key: return i else: return "不存在" def main(): alist = [5,3,7,2,12,45,16,23] #测试列表 print("所要查找的元素的位置是：",sequential_search(alist, 12)) #查找数据12 print("所要查找的元素的位置是：",sequential_search(alist, 36)) #查找数据36 main() #调用main函数
运行结果：
2 在列表中顺序查找最大值和最小值。
def max_min(lst): max = min = lst[0] for i in range(len(lst)): if lst[i] > max: max = lst[i] if lst[i]< min: min = lst[i] return (max,min) def main(): alist = [5,3,7,2,12,45,16,23] #测试列表 print("列表中元素的(最大值,最小值)=",max_min(alist)) #查找列表的最大值最小值 main()
运行结果：
二 二分查找
1 针对有序表的二分查找，非递归实现。
def binary_search(lst, key): low = 0 #左边界 high = len(lst) - 1 #右边界 time = 0 #记录查找次数 while low <= high: #左边界小于等于右边界，则循环 time += 1 mid = (low + high)//2 if lst[mid]>key: #中间位置元素大于要查找的值 high = mid - 1 elif lst[mid]<key: low = mid + 1 else: print("折半查找的次数: %d" % time) print("所要查找的值在列表中的索引号是：", end='') return mid print("折半查找的次数: %d" % time) return '未找到' #查找不成功，'未找到' def main(): alist = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92] result = binary_search(alist, 13) print(result) main()
运行结果：
2 针对有序表二分查找，递归实现。
def binary_search(lst, low, high, key): mid = int((low + high)/2) if high < low: return False elif lst[mid]==key: print("所要查找的值在列表中的索引号是：", end='') return mid elif lst[mid]> key: high = mid - 1 return binary_search(lst, low, high, key) else: low = mid + 1 return binary_search(lst, low, high, key) if __name__=="__main__" : alist = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92] low = 0 high = len(alist) - 1 result = binary_search(alist, 0, high, 21) print(result)
运行结果：
三 插值查找
插值查找是在二分查找的基础上改进，二分查找中分点的计算公式：mid=(low+high)/2,即 mid=low+1/2*(high-low)
插值查找改进为：mid=low+(key-lst[low])/(lst[high]-lst[low])*(high-low)
插值查找代码的实现：
def interpolation_search(lst, low, high, key): time = 0 #用来记录查找次数 while low < high: time += 1 # 计算mid值是插值算法的核心代码 mid = low + int((high - low) * (key - lst[low])/(lst[high] - lst[low])) print("mid={0}, low={1}, high={2}".format(mid, low, high)) if lst[mid] > key: high = mid - 1 elif lst[mid] < key: low = mid + 1 else: print("插值查找%s的次数:%s"%(key, time)) #打印插值查找的次数 return mid print("插值查找%s的次数:%s"%(key, time)) return False def main(): alist = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92] low = 0 high = len(alist) - 1 interpolation_search(alist, low, high, 13) main()
运行结果：
四 总结：
这是用python实现基础的查找算法，每个算法的复杂度不同，运行效率也不同，由于时间问题没有仔细给出每个算法的复杂度，如果有兴趣的小伙伴可以去自己试一试每个算法的复杂度。
