二分查找算法示例
陈莎拉
在学习二分查找之前，我们先学习：
什么是搜索？
搜索是一种实用程序，可让用户查找数据库中保存的文档、文件、媒体或任何其他类型的数据。搜索的工作原理很简单，就是将条件与记录匹配并将其显示给用户。这样，最基本的搜索功能就可以正常工作。
什么是二分搜索？
二分搜索是一种高级搜索算法，用于从已排序的项目列表中查找和获取数据。其核心工作原理是将列表中的数据分成两半，直到找到所需的值并在搜索结果中显示给用户。二分搜索通常被称为 半区间搜索 或者 对数搜索.
二分查找如何工作？
二分查找的工作方式如下：
- 搜索过程从定位排序数据数组的中间元素开始
- 之后，将键值与元素进行比较
- 如果键值小于中间元素，则搜索分析上方的值到中间元素进行比较和匹配
- 如果键值大于中间元素，则搜索将分析较低的值到中间元素进行比较和匹配
二分查找示例
我们来看一个字典的例子。如果你需要查找某个单词，没有人会按顺序浏览每个单词，而是随机找到最近的单词来搜索所需的单词。
上图说明了以下内容：
- 您有一个 10 位数字的数组，需要找到元素 59。
- 所有元素都标有从 0 到 9 的索引。现在，计算数组的中间值。为此，您需要取索引左侧和右侧的值并将它们除以 2。结果是 4.5，但我们取的是最低值。因此中间值为 4。
- 该算法将从中间（4）到最低界限的所有元素删除，因为 59 大于 24，现在数组只剩下 5 个元素。
- 现在，59 大于 45 小于 63。中间是 7。因此右侧索引值变为中间 - 1，等于 6，而左侧索引值保持不变，即 5。
- 此时，您知道 59 在 45 之后。因此，左边的索引 5 也成为中间。
- 这些迭代持续到数组减少到只有一个元素，或者要查找的项目成为数组的中间。
例子2
让我们看下面的例子来理解二分搜索的工作原理
- 您有一个排序好的数组，其值范围是从 2 到 20，您需要找到 18。
- 下限和上限的平均值是 (l + r) / 2 = 4。正在搜索的值大于中间值 4。
- 小于中间值的数组值将被从搜索中删除，而搜索大于中间值 4 的值。
- 这是一个循环的划分过程，直到找到实际要搜索的项目。
为什么我们需要二分查找？
以下原因使得二分查找成为更好的搜索算法选择：
- 无论数据大小，二分查找都能有效地处理已排序的数据
- 二进制算法不是按顺序遍历数据进行搜索，而是随机访问数据以查找所需元素。这使搜索周期更短且更准确。
- 二分查找根据排序原则对排序数据进行比较，而不是使用相等性比较，后者速度较慢且大多不准确。
- 每次搜索循环后，算法都会将数组的大小分为两半，因此在下一次迭代中，它将只对数组的剩余一半进行操作
学习我们的下一个教程 线性搜索： Python, C++ 例如：
结语
- 搜索是一种实用程序，可让用户搜索文档、文件和其他类型的数据。二分搜索是一种高级搜索算法，可从排序的项目列表中查找并获取数据。
- 二分查找通常称为半区间查找或对数查找
- 它的工作原理是在找到所需元素时每次迭代将数组分成两半。
- 这个 二进制算法 通过将最左边和最右边索引值的总和除以 2 来取数组的中间值。现在，算法根据要查找的元素，从数组中间删除元素的下限或上限。
- 该算法随机访问数据以查找所需元素。这使得搜索周期更短且更准确。
- 二分查找根据排序原则对已排序的数据进行比较，而不是使用速度慢且不准确的相等比较。
- 二分查找不适用于未排序的数据。
