关于数据结构，一个非常有趣的话题是搜索”。
现在，让我们首先理解你所说的搜索在非技术术语中的含义。搜索只是指找到特定的元素或事物。我们经常寻找丢失的或杂乱无章的东西。例如，我在学习桌上找不到我的蓝色钢笔。我到处都找遍了。在我们的日常生活中，我们都因这一术语而闻名。现在让我们来探讨一下它在技术语言中的含义。
一个搜索操作用于从提供的任何数据结构中查找或检索元素。一旦找到了需要的元素，就可以对其进行相应的操作。它是一种从定义类型下的许多对象的集合中查找特定对象的算法。
根据搜索类型将搜索进一步分为两种类型。
- 顺序搜索
- 区间搜索
顺序搜索
根据其名称，将依次遍历提供的列表或数组，直到找到元素为止。例如;线性搜索
区间搜索
这种类型的算法特别用于排序类型的数据结构。它们比线性搜索算法更复杂、更有效。它们针对的是“分而治之”策略，即将元素分成两部分，然后计算数组的中间元素。例如;二进制搜索。
我们已经讨论了搜索算法的基本介绍。现在让我们来详细探讨一下
首先，我们将知道线性搜索和二分搜索的区别。
表格形式的线性搜索和二分搜索的区别
| 线性搜索 | 二分查找 |
| 线性搜索是一种搜索算法，用于通过搜索直到找到列表中的元素。 | 二分查找是一种搜索算法，用于查找目标元素在已排序数组中的位置。 |
| 线性搜索也称为顺序搜索。 | 二分搜索又称为半区间搜索和对数搜索。 |
| 它的工作原理是一次扫描一个元素而不跳过另一个元素。 | 它的工作原理是将数组分成两半并计算中间元素。 |
| 线性搜索的实现很容易 | 二分查找的实现是复杂的 |
| 线性搜索的时间复杂度为O(N) | 二分查找的时间复杂度为O(log)2n) |
| 线性搜索可以在单链表、双链表、矢量表上实现 | 二进制搜索只能在允许双向遍历的数据结构上实现。 |
| 在搜索任何元素之前，没有必要对数组进行排序 | 在搜索任何元素之前，必须对数组进行排序 |
| 线性搜索算法是迭代的 | 二分查找算法遵循分治法则 |
| 它包含更少的代码行 | 它包含更多行的代码 |
| 进行平等比较 | 进行排序比较 |
现在让我们详细地了解每一个。
什么是线性搜索?
线性搜索是一种逐行检查每个元素是否为所需元素的搜索类型。如果选中了列表或数组中的所有元素，但没有一个元素是需要的，则搜索将不会成功。在这种情况下，最坏的情况是O(n)，即搜索所需元素的概率是其等效的比较次数，其中n是当前元素的数量。尽管最好的情况是O(1)，但所需要的元素是在第一个位置找到的。
如前所述，线性搜索是一种遍历序列中的元素的技术，因此称为顺序搜索。
为了使我们的概念更清楚，让我们考虑一个例子。考虑一个大小为100的数组。在这里，最好的情况是期望的元素将在O(1)中找到，而最坏的情况是O(100)，因为有100个元素需要比较。
在此基础上，我们知道线性搜索是非常容易和简单的实现。当列表有有限/少数元素或无序列表执行单个搜索时，它是实用的。
什么是二分查找?
二分查找是一种算法技术，计算是在列表的中间元素上完成的。它是非常高效和复杂的使用。二分查找的优点之一是它不扫描每个元素，而只搜索列表的一半。因此，执行搜索操作所需的时间更少。在开始搜索之前要考虑的一件事是，数组应该是有序的。正如上面所讨论的，这个搜索使用了分治技术，让我们看看它是如何精确地进行分治的。
下面是在二分查找中使用的三种情况:
情况1:数据< a[mid]，然后left = mid+1。
情况2:数据> a[mid] then right = mid-1
情形3:data =一个[mid] //元素被找到
这里a=数组名，mid=(左+右)/2
left是数组左边的下标right是数组右边的下标。
二分搜索的最佳情况与线性搜索相同，即O(1)。而最坏的情况是O(log2二进制搜索的应用是省时的，并且可以快速访问您正在搜索的元素。
在本文中，我们了解了搜索及其类型的重要概念。我们还讨论了他们的工作和效率。希望你能从这篇文章中得到一些相关信息。
作者
信心Changune
瑞典SVKM的杜勒理工学院
