时间戳

首页 > 解决方案 > 对字典中的项目进行二进制搜索

python - 对字典中的项目进行二进制搜索

问题描述

嗨，我有一个问题需要解决

要求是我必须使用它Binary Search Algorithm来执行此操作。

我有一本这样的字典：

inven = {1 : ["Lettuce", "Fresh Cut Lettuce", 1.30, 1000, False],
             2 : ["Apple", "Red big and round", 1.20, 1000, False],
             3 : ["Orange", "Orange big and round", 1.10, 1000, False],
             4 : ["Peach", "Pink big and round", 1.50, 1000, False],
             5 : ["Pear", "Green big and semi round", 1.30, 1000, False],
             6 : ["Plum", "Red small and round", 0.60, 1000, False]}

所以这个字典的键是1,2,3,4,5,6，值是键所属的列表。

我想使用Binary Search Algorithm来查找key值"Orange"所属的。

我这可能吗？另外，如果不可能，请指导我找到Algorithm可以为我解决这个问题的人。请我知道我可以运行一个for循环并解决这个问题，但这是我使用算法的要求。

标签： pythonalgorithm

解决方案

使用这些键，您不能使用二进制搜索，但如果您使用正确的排序键，您将能够根据需要应用任何搜索算法。

您可以通过计算每个单词的值来获取真正的键，在 Python 中，有一个函数调用ord，可以根据 ASCII/UNICODE 表将字符转换为 int 值。因此，您可以使用如下函数计算密钥：

def key_calculator(word: str) -> int:
    """
    This function converts any string to integer key. 

    pseudocode: 
        key_value = 0
        for each character in the string: 
            key_value += (character index) + (character value)
    """
    # init key_value
    key_value = 0
    # itarate in word length range
    for i in range(len(word)):
        # add the character index with the character value.
        # convert the letter to lower to avoid case sensitivity.
        key_value += i + ord(word[i].lower())
    # return the key
    return key_value

现在您可以使用以下函数计算每个单词键：

inven = {key_calculator(value[0]): value for _, value in inven.items()}

这将给我们这个 dict 结果：

inven = {
    779: ["Lettuce", "Fresh Cut Lettuce", 1.3, 1000, False],
    540: ["Apple", "Red big and round", 1.2, 1000, False],
    651: ["Orange", "Orange big and round", 1.1, 1000, False],
    523: ["Peach", "Pink big and round", 1.5, 1000, False],
    430: ["Pear", "Green big and semi round", 1.3, 1000, False],
    452: ["Plum", "Red small and round", 0.6, 1000, False],
}

最后一步是根据键对字典进行排序：

# sort inven dict keys 
sorted_keys = sorted(inven.keys())

# sort inven dict based on sorted_keys
inven = {key: inven[key] for key in sorted_keys}

这将为我们提供排序的 dict 结果：

inven = {
    430: ["Pear", "Green big and semi round", 1.3, 1000, False],
    452: ["Plum", "Red small and round", 0.6, 1000, False],
    523: ["Peach", "Pink big and round", 1.5, 1000, False],
    540: ["Apple", "Red big and round", 1.2, 1000, False],
    651: ["Orange", "Orange big and round", 1.1, 1000, False],
    779: ["Lettuce", "Fresh Cut Lettuce", 1.3, 1000, False],
}

现在您可以使用任何搜索算法通过以下步骤查找单词：

  • key_calculator使用函数将目标词转换为键。
  • 使用搜索算法，例如二分搜索。

或者

您可以使用此语法随机访问任何密钥inven[key_calculator('Orange')]。

推荐阅读