110 lines
4.8 KiB
Markdown
110 lines
4.8 KiB
Markdown
# 搜索实现:线性和二进制
|
||
|
||
> 原文：<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
|
||
|
||
#### 代码
|
||
|
||
```py
|
||
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。
|
||
|
||
```py
|
||
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，以便更好地理解。
|
||
|
||
尝试一下 [这个](https://www.cs.usfca.edu/~galles/visualization/Search.html) 动画可以更好地理解这两种搜索算法。尝试找到数组的第一个元素。哪个更快？
|
||
|
||
## 结论
|
||
|
||
从上面的解释中，很明显二分搜索法总是比线性搜索更快。如果你熟悉 o(n)符号，线性搜索是 o(n)，二分搜索法是 log(n)
|
||
|
||
您可以在一个排序列表上执行线性搜索，也可以进行一个小的优化。一旦要查找的数字超过了要比较的元素，就可以停止搜索。例如，你想从列表[2，4，5，13，16，19]中搜索 12，一旦搜索到 13，你就可以停止，因为在一个排序列表中，12 不可能排在 13 之后。
|
||
|
||
在本教程中，我们只讨论了二分搜索法迭代法。尝试自己实现递归方法。此外，了解这些搜索的用途以及何时应用它们。本教程到此为止。快乐的蟒蛇！ |