如何使用二进制搜索来搜索大量名称

Question

我是新来的 python 我正在对数组长度为 258000 的值的大数组执行二进制搜索，我已经在线性搜索上测试了我的代码，当它超过最大递归时它也会崩溃深度，这就是我使用二进制文件的原因。但是二进制也不能在那个大数组上工作，因为我在小数组上测试我的代码它工作正常，这是一个代码：

A = ['John', 'William', 'James', 'Charles', 'George', 'Frank']
names = sorted(A)
print(names)
n = len(names) - 1

low = 0
high = n
key = "James"

def binarysearch(a, l, h, k):

    if h < l:
        return l - 1
    mid = l + (h - l // 2)
    if k == names[mid]:
        return mid
    elif key < names[mid]:
        return binarysearch(a, l, mid-1, k)
    else:
        return binarysearch(a, mid+1, h, k)

index = binarysearch(names, low, high, key)

print("The given Name ", key, "is a Place ", index)

我知道如何增加 sys.setrecursionlimit() 我试过了，但它仍然会死，因为它超过了 RAM 限制，I have use bisect code of python and it works fine，但因为我是 python 的新手，所以我想吸收深入的算法概念，而不是内置函数，如果有人能帮助我更正这段代码，我将不胜感激，谢谢

Answer 1

这不是一个巨大的列表，只需使用 list.index。

x = [random.random() for _ in range(258000)] + [0.99]
%timeit x.index(0.99)
# 7.97 ms ± 703 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

示例

a = ['John', 'William', 'James', 'Charles', 'George', 'Frank']
a.index('James')  # --> 2

Answer 2

你根本不需要递归。您可以以迭代方式进行二进制搜索。但是，即使使用递归，您也不应使用此类数组达到最大递归深度。你打这个的原因是你没有正确地进行二进制搜索。

mid = l + (h - l // 2)

这显然是错误的，因为 l // 2 将首先被评估。你要的是：

mid = l + (h - l) // 2

此外，当 h < l 时，我不明白 returning l - 1 的合理性。通常你应该 return -1 来表示找不到密钥。 l - 1 在某些递归步骤中可能会为初始调用提供有效索引。

最后，如果列表未排序，则没有必要先对其进行排序然后进行二分查找，除非您对同一个数组进行大量查找，因为排序比简单的线性查找需要更多时间.

Answer 3

如果字符串数组在很长一段时间内不会发生变化，或者不会经常变化并且搜索将被非常频繁地使用，那么您可以使用 Trie 数据结构，这将以 space 复杂度为代价提高时间复杂度。最差时间复杂度为 O(length of the longest string in that array)

如何使用二进制搜索来搜索大量名称

how to search a big array of names using binary search

python

sorting

algorithm

binary-search