二分查找递归和非递归解读

二分查找是一种常用的查找算法，可以在有序的数组中快速查找目标元素，其时间复杂度为 O(log n)。在实现二分查找时，可以采用递归或非递归的方式。

递归实现二分查找的过程：

1. 如果 low > high，则表示查找失败，返回 -1。
2. 如果 low <= high，则计算 mid = low + (high - low) / 2，即中间位置的下标。
3. 如果 arr[mid] 等于目标元素 target，则直接返回 mid。
4. 如果 arr[mid] 大于目标元素 target，则在前半部分继续查找，即递归调用 binarySearch(arr, low, mid - 1, target)。
5. 如果 arr[mid] 小于目标元素 target，则在后半部分继续查找，即递归调用 binarySearch(arr, mid + 1, high, target)。

非递归实现二分查找的过程：

1. 如果 low > high，则表示查找失败，返回 -1。
2. 如果 low <= high，则计算 mid = low + (high - low) / 2，即中间位置的下标。
3. 如果 arr[mid] 等于目标元素 target，则直接返回 mid。
4. 如果 arr[mid] 大于目标元素 target，则在前半部分继续查找，即将 high 更新为 mid - 1。
5. 如果 arr[mid] 小于目标元素 target，则在后半部分继续查找，即将 low 更新为 mid + 1。
6. 重复步骤 1~5，直到找到目标元素或查找失败。

递归和非递归实现的二分查找算法本质上是一样的，只是实现方式不同。相对而言，递归实现简单易懂，但由于递归调用可能会产生大量的函数调用开销，因此在处理大规模数据时，非递归实现更为高效。