Python中的搜索算法。 #Python 系列 - 9

所以 到目前为止，我们已经学习了python的基础知识。但是，我们从未见过这些基本原理的应用。在本文中，我们将看到两种处理在列表中搜索数字的简单算法。如果您是算法的初学者和新手，那么开始使用算法可能会非常棘手，本文将为您减轻负担。让我们开始吧。

在搜索算法方面，有两种算法在编码社区中非常有名（即线性搜索和二进制搜索）。

线性搜索

根据维基百科，线性搜索的定义是“ 线性搜索 或者 顺序搜索 是一种在列表中查找元素的方法。它会依次检查列表中的每个元素，直到找到匹配项或搜索到整个列表。”

简而言之，从列表（Index-0）开始，逐个搜索，直到找到要搜索的元素。比如我需要在列表[7,2,0,7,2,3,5,9,5]中找到3

List-1

我们从索引 0 开始，

是 3 存在于索引 0 → 否，

是 3 存在于索引 1 → 否，

是 3 存在于索引 2 → 否，

是 3 存在于索引 3 → 否，

是 3 存在于索引 4 → 否，

在 index-5 中是 3 → 是的。 停止返回索引号，即 5

在最坏的情况下，您需要查找的号码可能不在列表中。当您到达列表末尾时，只需返回 -1。

让我们在 python 代码中尝试同样的方法。

 def binary_searching(my_list, element):  
 我 = 0  
 当我 < len(my_list):  
 如果 my_list[i] == 元素：  
 返回我  
 我 = 我 + 1  
 别的：  
 返回 -1  
  
  
 如果 __name__ == "__main__":  
 my_list = [7, 2, 0, 7, 2, 3, 5, 9, 5]  
 元素 = 3  
 idx = binary_searching（my_list，元素）  
 打印（idx）

线性搜索的时间复杂度是 上） 因为它在最坏的情况下会遍历整个列表。

相同的空间复杂度是 O(1) 因为除了输入列表之外它不占用任何空间。

二进制搜索

与线性搜索相比，二分搜索高效且快速，但主要缺点是为了执行二分搜索，我们需要对列表进行排序。

二进制搜索工作在两个指针方法中，我们需要两个指针在列表的两个极端索引上说 开始 和 结尾 .

根据 start 和 end，我们找到 mid =(start + end) / 2。现在，我们将 mid 索引值与要查找的元素进行比较。

情况1： 如果中间索引中的值等于元素，那么我们只返回中间索引。

案例2： 如果 mid Index 中的值大于 element，则调整 结束 = 中 - 1 .原因是如果中间索引中的值大于元素，那么从中间索引到结束索引的所有值都大于我们正在搜索的元素。所以，我们可以忽略这些指标。

案例3： 如果 mid Index 的值小于 element，即使这样我们也需要调整 开始 = 中间 + 1 .原因显而易见。如果中间索引中的值较小，则中间索引以下的所有值也较小。

我们将继续此操作，直到起始值小于结束值。如果它们相互交叉，那么我们退出循环，然后通过返回 -1 说没有找到我们正在搜索的元素。

用于二进制搜索的 Python 代码

 def binary_searching(my_list, element):  
 开始 = 0  
 结束 = len(my_list) - 1  
 而开始<=结束：  
 mid = (start + end) // 2 # 整数除法  
 如果 my_list[mid] < 元素：  
 开始 = 中间 + 1  
 elif my_list[mid] > 元素：  
 结束 = 中 - 1  
 别的：  
 return mid # my_list[mid] == 元素  
 别的：  
 返回 -1  
  
  
 如果 __name__ == "__main__":  
 my_list = [1, 4, 6, 8, 9, 10, 14, 17, 18]  
 元素 = 19  
 ans = binary_searching（my_list，元素）  
 打印（回答）

二分搜索的时间复杂度是 O（登录） 对于列表中的 100 个元素，我们在循环中仅迭代 6-8 个项目。这些时间复杂度有数学推导，我们将在以后的文章中介绍。

空间复杂度为 O(1)，除了变量，我们还没有创建任何数据结构。

很快再见到你的排序算法......

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/3000/58273108