二分查找:二分查找这个概念是非常简单的一个算法,也就是我们俗称的折半查找,原理是在一个有序的数组中,先取中间的值,
如果中间值大于或者小于我们需要查找的值,那么就舍弃一般,在另一半中进行查找.
""" 说明:对已经排好序列的列表数据进行查找 函数:二分查找 参数:list key 返回值:mid(所要查找到数据所在的序列) times(查找次数) """ def binary_search(list,key):length = len(list)low = 0 heigth = length -1 time = 0 while low <= heigth:time += 1 mid = int((low + heigth) / 2)if key > list[mid]:low = mid + 1 elif key <list[mid]:heigth = mid - 1 else:print("times: %s" % time)return midif __name__ =='__main__':LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]result = binary_search(LIST, 99)print(result)
运行结果:
插值查找:
这种方式的查找其实是将值构造成了一颗二叉排序数,然后进行查找.这种搜索的好处在于大大的缩短了搜索时间,时间复杂度为logn 小于线性的n
而插值查找则比较灵活,并不是简单的从中间进行的,它是根据我们需要查询的值的渐进进行搜索的.
插值查找的不同点在于每一次并不是从中间切分,而是根据离所求值的距离进行搜索的.
""" 说明:对已经排好序列的列表数据进行查找 函数:插值查找 参数:list key 返回值:mid(所要查找到数据所在的序列) times(查找次数) """ def binary_search(list,key):length = len(list)low = 0 heigth = length -1 time = 0 while low <= heigth:time += 1 mid = low + int((heigth - low) * (key - list[low])/(list[heigth] - list[low]))if key > list[mid]:low = mid + 1 elif key <list[mid]:heigth = mid - 1 else:print("times: %s" % time)return midif __name__ =='__main__':LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]result = binary_search(LIST, 444)print(result)
运行结果:
更多推荐
静态,插值,列表,python
发布评论