搜索算法简介
原文：https://www.studytonight.com/data-structures/search-algorithms
甚至没有一天的通行证，当我们不必在我们的日常生活中寻找一些东西，车钥匙，书，笔，手机充电器和什么没有。计算机的生命也是如此，其中存储着如此多的数据，以至于每当用户要求一些数据时，计算机都必须搜索它的内存来寻找数据，并使其对用户可用。而且电脑有它自己的快速搜索内存的技术，你可以在我们的操作系统教程系列中了解更多。
如果你必须写一个程序来搜索一个数组中的一个给定的数字呢？你会怎么做？
要搜索给定数组中的元素，有两种流行的算法:
- 线性搜索
- 二进位检索
线性搜索
线性搜索是一种非常基本和简单的搜索算法。在线性搜索中，我们通过从头开始遍历数组来搜索给定数组中的元素或值，直到找到所需的元素或值。
它将待搜索的元素与数组中存在的所有元素进行比较，当元素匹配成功时，它返回数组中元素的索引，否则返回-1。
当列表中的元素较少时，线性搜索适用于未排序或无序的列表。
线性搜索算法的特点
- 它用于未排序和无序的元素小列表。
- 它的时间复杂度为 O(n) ，也就是说时间线性依赖于元素的数量，这不算差，但也没那么好。
- 它有一个非常简单的实现。
我们将在下一个教程中实现线性搜索算法。
二进位检索
二分搜索用于排序数组或列表。在二分搜索，我们遵循以下步骤:
- 我们从比较要搜索的元素和列表/数组中间的元素开始。
- 如果我们得到匹配，我们返回中间元素的索引。
- 如果我们没有得到匹配，我们检查要搜索的元素在值上是小于还是大于中间元素。
- 如果要搜索的元素/数字的值大于中间数字，那么我们选择中间元素右侧的元素(当列表/数组被排序时，因此在右侧，我们将拥有大于中间数字的所有数字)，并从步骤 1 重新开始。
- 如果要搜索的元素/数字的值小于中间的数字，那么我们选择中间元素左侧的元素，并从步骤 1 重新开始。
当一个数组中有大量元素并且它们被排序时，二分搜索是有用的。
所以二分搜索工作的一个必要条件是列表/数组应该被排序。
二分搜索的特色
- 在大的排序数组中搜索是很棒的。
- 它的时间复杂度为 O(log n) ，这是一个非常好的时间复杂度。我们将在二分搜索教程中详细讨论这一点。
- 它的实现很简单。