您好,这里:)我正在写一个程序,它使用二进制搜索排序列表。它的工作原理如下: python find.py 3 1 2 3
程序应在数字1、2和3中查找3
如果它不在%1、%2和% 3中,则应返回true并打印找到的针;如果应返回false,则打印未找到...
def binary_search(needle, haystack):
first = 0
last = len(haystack) - 1
itemlist = str(input(haystack))
sorted(itemlist)
while first <= last:
mid = (first + last) / 2
if itemlist[mid] == needle :
print("Found the needle in the haystack")
return True
elif needle < itemlist[mid]:
last = mid - 1
else:
first = mid + 1
if not True:
print("Did not find the needle in the haystack")
return False
所以我尝试实现了一个标准的二进制搜索算法,但我遇到的每个版本都不会将第一个数字作为你需要在接下来的所有数字中搜索的项目……所以我的问题是,如何将第一个变量设置为“项目”,然后将所有内容设置为一个可能包含或不包含该项目的列表?
我还需要对x长度的列表进行排序,所以我尝试了排序函数,但是因为列表可以是任意长度的,所以我需要对变量进行排序?我被困在那里了.关于这些话题有什么建议吗?
发布于 2017-12-01 21:39:35
二进制搜索是标准库的一部分。以下是如何使用它来解决您的问题:
import sys
import bisect
argv = [int(_) for _ in sys.argv[1:]]
x = argv.pop(0)
i = bisect.bisect_left(argv, x)
print("Found:", i != len(argv) and argv[i] == x)
此外,只有在输入列表已经排序的情况下,问题才有意义。如果不是,只需使用x in argv
,它是线性的(对列表进行排序是线性的)。
https://stackoverflow.com/questions/47593472
复制相似问题