geekdoc-python-zh/docs/pythoncentral/search-implementations-linear-binary.md

搜索实现:线性和二进制

原文：https://www.pythoncentral.io/search-implementations-linear-binary/

先决条件

要了解线性和二分搜索法，你需要很好地理解:

1. Python 3
2. 基本 Python 数据结构概念-列表

简介

我们经常需要从给定的数据结构中找到一个元素，比如列表、链表或二叉树。有效的搜索技术可以节省大量时间并提高性能。在本教程中，我们将看到两个非常常用的搜索算法。

线性搜索

那么，如果你要在一个光线不好的房间里从书架上搜索“哈利·波特”，你会怎么做呢？你会从一端开始，一次拿一本书，检查它是不是哈利波特。你将使用蛮力方法检查每一本书，直到找到哈利波特或到达书架的尽头。最好的情况是哈利波特是第一本书，最坏的情况是这本书根本不在里面。无论哪种方式，你只能通过检查每一本书来了解这一点。这正是线性搜索。

二分搜索法

如果你要从一个按字母顺序排列的书架上寻找哈利波特，会怎么样？你会从头开始搜索吗？肯定不是！你可以从中间附近的某个地方开始，检查书籍的第一个字母，然后从那里向前或向后查找“H”标题。这意味着你不会看所有的书，从而节省时间。你也不需要翻遍整个书架来知道这本书是否在那里。在某一点上，你正在淘汰许多你永远不会看的书。二分搜索法与此类似。

注意: 可以对排序和未排序的项目进行线性搜索，但只能对排序后的项目集进行二分搜索法。

实施

现在你已经知道了什么是线性和二分搜索法方法，让我们看看这些搜索是如何在一系列数字上工作的。

线性搜索

给定列表 A = [6，3，9，0，5，8，2]查找 0 是否出现在该列表中。

算法

1. 从列表 A 中一次取出一个数字
2. 与 0 比较，检查是否匹配:
   1. 如果是，返回 True
   2. 如果不是，返回 False
3. 如果列表结束，返回 False

代码

def linearSearch(ls,data):

   for item in ls:
       if item == data:
           return True
   return False

print(linearSearch([6，3，9，5，8，2]，0))

二分搜索法

这个想法是不断比较元素和中间值。这样，每次搜索我们都会删除一半的列表。

算法

1. 保持跟踪两个指针，第一个和最后一个，它们被递增或递减以限制要搜索的列表部分。
2. 找到列表的中间元素:mid =(列表长度)/2
3. 将中间元素与要查找的值进行比较
4. 检查中间元素是否小于要查找的值:
   1. 如果是，该元素必须位于列表的后半部分
   2. 如果不是，元素必须位于列表的前半部分
5. 重复第 1 步到第 3 步，直到找到元素或到达列表的末尾

注意: 列表继续被一分为二，中间的元素被比较，直到找到该元素或者没有其他元素可以比较。

代码

给定列表 B = [2，5，7，8，9，11，14，16]找出列表中是否有 14。

def binarySearch(ls,data):
   first = 0
   last = len(ls)-1
   done = False   

    while first<=last and not done:
       mid = (first+last)//2
          if ls[mid] == data:
           done = True
       else:
           if ls[mid] > data:
               last = last-1
           else:
               first = first+1
   return done 

print(binarySearch([2,5,7,8,9,11,14,16],4))

| 回合 | 第一次 | 最后一次 | 中旬 | ls[mid] | 结果 | | 1 | 0 | 7 | 3 | 8 | 8 < 14 | | 2 | 4 | 7 | five | Eleven | 11 < 14 | | three | six | seven | six | Fourteen | 14=14 |

注: 求 mid 元素，用“(first+last)//2”代替“(first+last)/2”。这给了我们整数，特别是当列表的长度是奇数时。在您的 Python IDLE 中尝试 9/2 和 9//2，以便更好地理解。

尝试一下 这个 动画可以更好地理解这两种搜索算法。尝试找到数组的第一个元素。哪个更快？

结论

从上面的解释中，很明显二分搜索法总是比线性搜索更快。如果你熟悉 o(n)符号，线性搜索是 o(n)，二分搜索法是 log(n)

您可以在一个排序列表上执行线性搜索，也可以进行一个小的优化。一旦要查找的数字超过了要比较的元素，就可以停止搜索。例如，你想从列表[2，4，5，13，16，19]中搜索 12，一旦搜索到 13，你就可以停止，因为在一个排序列表中，12 不可能排在 13 之后。

在本教程中，我们只讨论了二分搜索法迭代法。尝试自己实现递归方法。此外，了解这些搜索的用途以及何时应用它们。本教程到此为止。快乐的蟒蛇！