常用算法完成二分查找

敬请关注李永平所运营的个人微信公众号平台

二分搜索（折半搜索）是一种针对有序数组中特定元素进行查找的算法。

问题描述：

给定一个有序数组，输入一个数值，判断该数值是否存在于数组中。

问题分析：

由于数组本身具有有序性，因此在查找某个数值是否存在时，可以采用折半查找的方法。具体而言，需要设定数组的左边界与右边界，并计算出中间位置的数值。将该中间值与目标值进行比较：若中间值大于目标值，则说明目标值位于数组的前半部分，此时应将右边界调整为中间位置减一；反之，若中间值小于目标值，则表明目标值位于后半部分，此时应将左边界调整为中间位置加一。

重复上述步骤直至找到该数值或确认其不存在于数组中。

循环结束的条件包括：当左边界超过右边界时或者成功找到目标数并返回结果。

实现该算法有两种方式：递归法与非递归法。

时间复杂度

该算法基于分治策略，在最坏情况下两种实现方式的时间复杂度相同：O(log2 N)，而在最佳情况下则为O(1)。

空间复杂度

算法的空间复杂度并非指实际占用的空间大小，而是衡量整个过程中所需的辅助存储单元数量。

对于非递归方法而言，所需辅助空间为常数级别，因此其空间