c++ 二分查找（迭代与递归）

��       二分搜索被定义为一种在排序数组中使用的搜索算法，通过重复将搜索间隔一分为二。二分查找的思想是利用数组已排序的信息，将时间复杂度降低到O(log N)。

 二分查找算法示例

何时在数据结构中应用二分查找的条件：

应用二分查找算法：

        1、数据结构必须是有序的。

        2、访问数据结构的任何元素都需要恒定的时间。
二分查找算法：

        在这个算法中， 通过查找中间索引“mid”将搜索空间分为两半。 

在二分查找算法中查找中间索引“mid”  

1、将搜索空间的中间元素与键进行比较。 

2、如果在中间元素找到密钥，则过程终止。

3、如果在中间元素没有找到键，则选择哪一半将用作下一个搜索空间。

        3.1、如果键小于中间元素，则使用左侧进行下一步搜索。

        3.2、如果键大于中间元素，则使用右侧进行下一步搜索。

4、这个过程一直持续到找到密钥或者总搜索空间耗尽为止。

二分查找如何工作？

要了解二分搜索的工作原理，请考虑下图：

考虑一个数组arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}，目标 = 23。
第一步：计算mid并将mid元素与key进行比较。如果键小于 mid 元素，则向左移动，如果大于 mid 则将搜索空间向右移动。

        键（即 23）大于当前中间元素（即 16）。搜索空间向右移动。

二分查找算法：将键与 16 进行比较  

密钥小于当前的中间 56。搜索空间向左移动。  

二分查找算法：将键与 56 进行比较 

第二步：如果key与mid元素的值匹配，则找到该元素并停止搜索。 

二分搜索算法：与 mid 的关键匹配 

如何实现二分查找？

二分查找算法可以通过以下两种方式实现

    1、迭代二分搜索算法

    2、递归二分查找算法

下面给出了这些方法的伪代码。
1.迭代二分查找算法：

这里我们使用 while 循环来继续比较键并将搜索空间分成两半的过程。

迭代二分搜索算法的实现：  

// C++ program to implement iterative Binary Search

#include

using namespace std;

// An iterative binary search function.

int binarySearch(int arr[], int l, int r, int x)

{

    while (l