用递归与非递归实现二分查找

题目

• 考察点：算法
• 难度： 中等
• 题目：使用递归与非递归的方式实现二分查找

题目解析

非递归方式实现（Python）

def search(ordered_array, item):
    """
    ordered_array：有序数组
    item：被查找的元素
    """
    left, right = 0, len(ordered_array) - 1
    while left <= right:
        middle = (left + right) // 2
        if item < ordered_array[middle]:
            right = middle - 1
        elif item > ordered_array[middle]:
            left = middle + 1
        else:
            return middle
    return -1

• 测试用例

def test_search():
    array = [1, 2, 3, 4, 5]
    assert search(array, 1) == 0
    assert search(array, 2) == 1
    assert search(array, 3) == 2
    assert search(array, 4) == 3
    assert search(array, 5) == 4

递归方式实现（Python）

def recursion_search(ordered_array, left, right, item):
    """
    ordered_array: 有序数组
    left： 最左边的索引，初始为0
    right： 最右边的索引，初始为长度-1
    item：被查找的元素
    """
    if right >= left:
        mid = int(left + (right - left) / 2)
        if ordered_array[mid] == item:
            return mid
        elif ordered_array[mid] > item:
            return recursion_search(ordered_array, left, mid - 1, item)
        else:
            return recursion_search(ordered_array, mid + 1, right, item)
    else:
        return -1

• 非递归方式

def test_recursion_search():
    arr = [2, 3, 4, 10, 40]
    assert recursion_search(arr, 0, len(arr) - 1, 2) == 0
    assert recursion_search(arr, 0, len(arr) - 1, 3) == 1
    assert recursion_search(arr, 0, len(arr) - 1, 4) == 2
    assert recursion_search(arr, 0, len(arr) - 1, 10) == 3
    assert recursion_search(arr, 0, len(arr) - 1, 40) =