我是编程算法的新手,遇到了在python中实现未排序列表的二进制搜索的问题。我想好了如何实现下面的递归二进制搜索函数,但在递归深度限制方面遇到了一些麻烦。所以我很好奇是否有另一种方法可以在python中实现对未排序列表的二进制搜索:
def binary_search_unsorted(unsortedList, target):
if len(unsortedList) == 0:
return False;
else:
start = unsortedList[0];
if start == target:
return True;
else:
if start < target:
return binary_search_unsorted([n for n in unsortedList if n > start], target);
else:
return binary_search_unsorted([n for n in unsortedList if n < start], target);
无论如何实现,对任何类型的未排序数据结构的二进制搜索都是徒劳的,毫无意义。
二进制搜索的前提是,它可以通过查看当前值并将其与目标值进行比较来排除大部分搜索空间,因为由于数据结构经过排序,它可以对这些元素进行假设。
再次思考您试图解决的问题,并向提供该问题的来源询问一些严肃的问题。
由于您只使用尾部递归(也就是说,除了返回其结果之外,您从不使用递归调用做任何事情(,因此可以以非常直接的方式将其重写为带递归的循环。