递归与非递归的二分搜索算法对比

# 1. 算法简介

在本章中，我们将介绍二分搜索算法的概念，并对递归和非递归算法进行简要描述。让我们一起深入了解这些算法的基本原理和特点。

# 2. 递归二分搜索算法

二分搜索是一种常见的查找算法，递归二分搜索算法则是在这个基础上使用递归实现。接下来我们将详细介绍递归二分搜索算法的实现原理、调用过程分析以及时间复杂度和空间复杂度的分析。

# 3. 非递归二分搜索算法

在本章节中，我们将详细介绍非递归二分搜索算法的实现原理、循环过程分析以及时间复杂度和空间复杂度的分析。

#### 3.1 算法实现原理

非递归二分搜索算法采用循环结构来实现，其基本思想是通过对有序数组中间元素与目标值的比较，来决定继续搜索的半区间。具体步骤如下：

1. 初始化左指针 `low` 指向数组起始位置，右指针 `high` 指向数组末尾位置。
2. 在循环中，计算中间位置 `mid = low + (high - low) // 2`，取中间元素 `nums[mid]` 与目标值 `target` 进行比较。
3. 若中间元素等于目标值，则返回中间位置 `mid`。
4. 若中间元素大于目标值，则将右指针 `high` 移动到 `mid - 1`。
5. 若中间元素小于目标值，则将左指针 `low` 移动到 `mid + 1`。
6. 重复步骤2至步骤5，直到找到目标值或左指针大于右指针。若找不到目标值，则返回 -1。

#### 3.2 非递归循环过程分析

下面通过具体的代码示例，演示非递归二分搜索算法的循环过程：

def binary_search(nums, target):
    low, high = 0, len(nums) - 1

    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# 示例
nums = [1, 3, 5, 7, 9]
target = 5
result = binary_search(nums, target)
print("目标值在数组中的索引为:", result)

#### 3.3 时间复杂度和空间复杂度分析