时间戳

首页 > 解决方案 > 递归二进制搜索无法系统地工作

python - 递归二进制搜索无法系统地工作

问题描述

我正在使用迭代和递归方法实现二进制搜索算法。

输入的第一行包含一个整数n和一个按升序排列的n成对不同的正整数序列。下一行包含一个整数k和k正整数。

对于i从 0 到的所有k - 1，输出一个0 <= j <= n-1这样的索引a_j = b_i，或者-1如果没有这样的索引。（对于每个算法实现）

a 和 b 分别是每个序列的元素。

输入：

5 1 5 8 12 13
5 8 1 23 1 11

输出：

2 0 -1 0 -1
2 0 -1 0 -1
2 0 -1 0 -1

我设法实现了迭代、递归版本和线性搜索版本。

import sys

def binary_search_it(a, x):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if x == a[mid]:
            return mid
        # left--mid--x--right
        if a[mid] < x:
            left = mid + 1
        # left--x--mid--right
        elif x < a[mid]:
            right = mid - 1
    return - 1

def binary_search_rec(a, x):
    left, right = 0, len(a) - 1
    if right < left:
        return left - 1
    mid = left + (right - left) // 2
    if x == a[mid]:
        return mid
    if x < a[mid]:
        return binary_search_rec(a[: mid - 1], x)
    else:
        return binary_search_rec(a[mid + 1:],x)


def linear_search(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n = data[0]
    m = data[n + 1]
    a = data[1 : n + 1]
    for x in data[n + 2:]:
        # replace with the call to binary_search when implemented
        print(binary_search_it(a, x), end=' ')
    print('\n')
    for x in data[n + 2:]:
        print(linear_search(a, x), end=' ')
    print('\n')
    for x in data[n + 2:]:
        print(binary_search_rec(a, x), end = ' ')

到目前为止一切都很好，对于上面的示例，代码为所有三个实现返回相同的输出。

如果我尝试使用另一个示例数据集，我的递归方法会出现问题

输入：

5 1 2 3 4 5
5 1 2 3 4 5

输出（预期）：

0 1 2 3 4
0 1 2 3 4
0 -1 2 0 0

有人可以解释一下我的代码中的流程以及您如何识别问题吗？

标签： pythonalgorithmrecursionsearch

解决方案

此实现存在多个问题：

  • 使用切片是昂贵的并且使这个算法O(n)

  • 递归算法永远不会返回-1以指示未找到该项目。

二分搜索的递归实现仍然需要跟踪left并right为O(log n)。

def binary_search_rec(a, x):
    return _binary_search(a, x, 0, len(a) - 1)

def _binary_search(a, x, left, right):
    if right < left:
        return -1

    mid = (right + left) // 2
    if x == a[mid]:
        return mid
    if x < a[mid]:
        return _binary_search(a, x, left, right - 1)
    else:
        return _binary_search(a, x, left + 1, right)

推荐阅读