在列表列表中搜索郊区

Question

我有一个列表列表，其中包含一组邮政编码和匹配的郊区。我需要创建一个迭代二分搜索算法，要求用户输入郊区的名称，然后程序输出郊区所属的邮政编码。该列表如下所示：

L = [['4000', 'Charlestown'], ['4001', 'Jamestown'], ['4002', 'Henrytown']]

因此，如果我要运行对此进行二进制搜索并且用户输入 'Jamestown'，那么程序将输出“4001”。这就是我创建二进制搜索函数所做的工作：

    suburb = input("Please enter the name of a suburb: ")

    def binarySearch(L, target):
        low = 0
        high = len(L)-1
        while low <= high:
            mid = (low + high)//2
            if L[mid] == target:
                return mid
            elif L[mid] > target:
                high = mid-1
            else:
                low = mid+1
    binarySearch(L, suburb)

但是，当我运行程序出现错误时：

elif L[mid] > target:
TypeError: '>' not supported between instances of 'list' and 'str'

我不太确定如何解决这个问题，如有任何帮助，我们将不胜感激。谢谢！

Answer 1

为此使用字典。让生活更轻松：

>>> d = {key: val for (val, key) in L}
>>> d['Jamestown']
'4001'

Answer 2

对于这种问题，如果你能将数据结构化为字典，你会更好，例如：

zips = { 'Charlestown': 4000, 'Jamestown': 4001,'Henrytown': 4002}

然后您可以一步查找任何郊区的邮政编码：

zips['Charlestown']

将评估为：

如果你有一堆这样的东西要查找，并且出于某种原因，数据是在列表中给你的，你可以从列表转换为字典。这个问题在这里得到了很好的回答：

Convert a list to a dictionary in Python

如果您被迫使用奇怪的数据结构来完成家庭作业练习，请参阅下面我为您提供的单独答案。

Answer 3

如果您真的打算使用列表，例如，如果这是为了家庭作业...

认识到您正在使用列表列表。因此，当您尝试将第 i 个列表 L[i] 与 suburb 的值进行比较时，您正在比较内部列表，例如 [4000, 'Charlestown'] 与 'Charlestown'

相反，您需要将 L[i][1] 与郊区进行比较。

此外，根据您提供的数据，该函数不会为您提供您想要的结果（尽管您会避免错误消息），即使您修复了该数据。二分查找很棒，但它需要根据您要查找的值对数据进行排序。

对此有一个建议：

sorted(L, key=lambda L_inner: L_inner[1])

看看你是否能自己弄清楚如何实现它。一些文档：https://docs.python.org/3/howto/sorting.html#sortinghowto

Answer 4

在这种情况下，您只需要修改二分查找功能即可。错误是您将列表与字符串进行比较（请参阅异常消息）。那是因为这一行：

L[mid] > target

其中 L[mid] 是一个元组，target 是一个字符串。请改用 L[mid][1] > target。

def binarySearch(L, target):
    low = 0
    high = len(L)-1
    while low <= high:
        mid = (low + high)//2
        if L[mid][1] == target:
            return mid
        elif L[mid][1] > target:
            high = mid-1
        else:
            low = mid+1

注意：这仅在您的列表按城镇名称排序时有效，否则您的搜索方向错误

Answer 5

问题是您有一个多维数组，并且您正试图将它与郊区的名称相匹配。您需要匹配每个嵌套数组的第二个元素。

   def binarySearch(L, target):
    low = 0
    high = len(L)-1
    while low <= high:
        mid = (low + high)/2
        if L[mid][1] == target:
            return L[mid][0]
        elif L[mid][1] > target:
            high = mid-1
        else:
            low = mid+1

请注意，我还返回了 L[mid][0]，它将为您提供密码而不是元素编号。

在列表列表中搜索郊区

Searching for a suburb in a list of list

python

binary

search

binary-search