首页 文章

已排序子列表的递归二进制搜索

提问于
浏览 次
0

我试图实现一个递归二进制搜索算法，它采用4个参数，一个列表，第一个，排序子序列中第一项的整数索引，最后一个，排序子序列中最后一项的整数索引和将与存储在列表中的值进行比较的目标 .

算法需要返回已排序子序列中目标的位置（如果存在），如果不返回它应放置在已排序子序列中的位置 .

这是我到目前为止所拥有的;

def binary_search(a_list, first, last, target):
    subMidpoint = (first + last) // 2
    if a_list[subMidpoint] == target:
        return subMidpoint
    else:
        if target < a_list[subMidpoint]:
            last = subMidpoint -1
            return binarySearch(a_list, first, last, target)
        else:
            first = subMidpoint +1
            return binarySearch(a_list, first, last, target)
    return first

如果项目不存在，我正在努力绕过它将如何返回位置，任何帮助将不胜感激 . 然而，当前编译的代码返回'None'而不是索引位置 .

提前谢谢了 .

编辑;

感谢大家的帮助，我设法改变了最后一个条款并且它已经通过了一些测试，但是当目标小于第一个最小值并且目标大于最后一个值时它失败了 .

这是改变后的最终条款 .

else:
    if target < a_list[subMidpoint]:
        last = subMidpoint -1
        return binary_search(a_list, first, last, target)
    else:
        first = subMidpoint +1
        return first
python algorithm recursion binary-search

2 回答

  • 0

    你几乎在你的描述中得到了你的答案：如果你得到相邻的项目，说第5和第6位，你就会在这种情况下返回两者中的较高者 - 6 .

    因此，你的逻辑将在你的最后一句中

    else:
    if subMidpoint == first:
        return last
    else:
        first = subMidpoint +1
        return binarySearch(a_list, first, last, target)

    • 将 return first 放在底部;你不应该达到那个陈述 .

    • 了解 elif 关键字;你的程序将更具可读性 .

    回复于
  • 0

    解决了，谢谢大家 . 不是最干净的解决方案，但它的工作原理 .

    def binary_search(a_list, first, last, target):
subMidpoint = (first + last) // 2
if target < a_list[first]:
    return first
elif target > a_list[last]:
    return last +1
elif a_list[subMidpoint] == target:
    return subMidpoint
elif target < a_list[subMidpoint]:
    last = subMidpoint -1
    return binary_search(a_list, first, last, target)
else:
    first = subMidpoint +1
    return first
    回复于

相关问题