查找算法

顺序查找

  • 当数据存储在诸如列表的集合中时,我们说这些数据具有线性或顺序关系。 每个数据元素都存储在相对于其他数据元素的位置。 由于这些索引值是有序的,我们可以按顺序访问它们。 这个过程产实现的搜索即为顺序查找。
  • 顺序查找原理剖析:
    • 从列表中的第一个元素开始,我们按照基本的顺序排序,简单地从一个元素移动到另一个元素,直到找到我们正在寻找的元素或遍历完整个列表。如果我们遍历完整个列表,则说明正在搜索的元素不存在。
 
  • 代码实现:该函数需要一个列表和我们正在寻找的元素作为参数,并返回一个是否存在的布尔值。found 布尔变量初始化为 False,如果我们发现列表中的元素,则赋值为 True。
  • 有序列表:之前我们列表中的元素是随机放置的,因此在元素之间没有相对顺序。如果元素以某种方式排序,顺序查找会发生什么?我们能够在搜索技术中取得更好的效率吗?
 
  • 二分查找:一定是只可以被应用在有序列表中
    • 有序列表对于我们的实现搜索是很有用的。在顺序查找中,当我们与第一个元素进行比较时,如果第一个元素不是我们要查找的,则最多还有 n-1 个元素需要进行比较。 二分查找则是从中间元素开始,而不是按顺序查找列表。 如果该元素是我们正在寻找的元素,我们就完成了查找。 如果它不是,我们可以使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素,就可以消除中间元素以及比中间元素小的一半元素。如果该元素在列表中,肯定在大的那半部分。然后我们可以用大的半部分重复该过程,继续从中间元素开始,将其与我们正在寻找的内容进行比较。

def sort(alist, item):  # item就是我们要找的元素
low = 0 # 进行二分查找操作的列表中第一个元素的下标
high = len(alist) - 1 # 进行二分查找操作的列表中最后一个元素的下标
find = False
# 判断是否比最大值大或最小值小
if item > alist[high] or item > alist[high]:
find = 'xx'

while low <= high:
mid = (low + high) // 2 # 中间元素的下标
if item > alist[mid]: # 我们要找的数比中间元素值大,则意味着我们要找的数在中间元素的右侧
low = mid + 1
elif item < alist[mid]: # 找的数比中间元素小,则意味着我们要找的数是在中间元素左侧
high = mid - 1
else: # 找到啦
find = True
break
return find

alist = [1,2,3,4,5,6,7]
print(sort(alist,8))
 
原文地址:https://www.cnblogs.com/blackball9/p/11889386.html