使用递归进行 Python 二分查找

在二分查找中，我们将项目集合分成两半，以减少查找元素所需的直接比较次数。但是，有一个要求：数组中的项目必须事先排序。

二分搜索

二分查找 方法用于定位列表中特定成员的索引。它是最受欢迎且最快的算法之一。为了使二分查找过程能够运行，列表中的条目应已排序。

与 线性查找 相比，二分查找 是一种更有效的查找元素索引的方法，因为我们不必检查列表中的每个索引。

二分查找算法的整个操作可总结为以下步骤：

• 定位已排序数组中的中间元素。
• 将要查找的元素与中间元素进行比较。
• 如果该元素等于给定列表的中间元素，则返回中间元素的索引。否则，算法将元素与中间项进行比较。
• 现在，如果待查找的元素大于列表的中间项，则将其与列表的右半部分进行比较，即中间索引之后的元素。
• 或者，如果元素小于列表中的中间元素，则仅与列表的左半部分进行比较，即中间索引之前的元素。

递归二分查找

二分查找意味着在已排序的数组中不断将搜索区间分成2个相等的部分来查找元素，而递归二分查找则涉及将整个二分查找过程分解为更小的问题。递归二分查找是二分查找的递归解决方案。

以下是所有递归解决方案必须满足的特性：

1. 递归方法需要一个基本情况。
2. 递归方法必须有一个递归测试用例。
3. 递归方法必须更接近基本情况。

基本情况代表复杂问题的最低细分，是一个最终情况。因此，要通过递归方法执行二分查找，我们的算法必须包含一个基本情况和一个递归情况，其中递归情况向基本情况进行。否则，该过程将永远不会结束，并导致无限循环。

二分查找技术可以减少在已排序数组中查找特定元素所需的时间。二分查找方法通常是迭代实现的，但我们也可以通过将其分解成更小的部分来递归实现它。

代码

输出

The given list is
[2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22]
Element searched is found at the index 2 of given list

递归是一种非常强大的编程和解决问题技术。我们可以使用它来评估和执行各种算法，从简单的迭代问题到复杂的回溯问题。在本教程中，我们研究了如何使用 Python 语言创建递归二分查找方法。