使用递归与非递归的方式实现二分查找

面试题
1

题目

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

题目解析

非递归方式实现（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) == 4
1 个赞