Python 3 二进制搜索一个排序变量（数字列表）

Question

你好 :) 我正在编写一个程序，该程序通过排序列表使用二进制搜索。它应该按如下方式工作：python find.py 3 1 2 3

程序应该在数字 1 2 和 3 中查找 3

如果在 1 2 和 3 中，它应该 return 为真并打印找到的针，如果它不在 1 2 和 3 if should return false and print did not find....

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

所以我尝试实现一个标准的二进制搜索算法，但是我遇到的每个版本都没有将第一个数字作为您需要在以下所有数字中搜索的项目... 所以我的问题是，如何将第一个变量设置为 "item"，然后将所有内容设置为可能包含也可能不包含该项目的列表？

我还需要对 x 长度的列表进行排序，所以我尝试了 sorted 函数，但是由于列表可以是任意长度，我需要对变量进行排序吗？我有点卡在那里....关于这些主题有什么提示吗？

Answer 1

sys.argv 是一个包含用于调用 python 进程的命令行参数的列表。 sys.argv[0] 是脚本的名称，sys.arv[1:] 是剩余的参数。像这样访问它：

def binary_search(needle, haystack):
    print('binary_search(): needle = {}, haystack = {}'.format(needle, haystack))
    # your implementation here

if __name__ == '__main__':
    import sys

    if len(sys.argv) > 2:
        needle = sys.argv[1]
        haystack = sys.argv[2:]
        binary_search(needle, haystack)
    else:
        print('Usage: {} needle haystack...'.format(sys.argv[0]))

如果您需要先对大海捞针进行排序，请使用sorted():

binary_search(needle, sorted(haystack))

然而，首先排序没有什么意义，因为它具有 O(n log n) 时间复杂度，而线性搜索只有 O(n ) 时间复杂度。因此，如果输入未排序，最好只通过遍历列表进行搜索，直到找到目标。

最后，您可能需要将输入转换为数值，以便进行搜索。您可以为此使用 int()：

        needle = int(sys.argv[1])
        haystack = [int(s) for s in sys.argv[2:]]

Answer 2

二分查找是标准库的一部分。以下是如何使用它来解决您的问题：

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，它是线性的（对列表进行线性排序）。

Python 3 二进制搜索一个排序变量（数字列表）

Python 3 binary search a sorted variable (list of numbers)

python

sorting

binary-search

python-3.x