Двоичный поиск элемента в словаре

Question

Привет, у меня есть проблема, которую мне нужно решить

Требования заключаются в том, что я должен использовать 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 l oop и решить эту проблему, но я обязательно использую алгоритм.

Answer 1

С этими ключами вы не можете использовать двоичный поиск, но если вы используете правильно отсортированные ключи, вы сможете применять любые алгоритмы поиска по своему усмотрению.

Вы можете получить реальные ключи путем вычисления значения каждого слова, в Python есть функция с именем ord, которая преобразует символ в значение типа int на основе таблицы ASCII / UNICODE. Таким образом, вы можете рассчитать свои ключи, используя такую ​​функцию:

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],
}

Последний шаг - отсортировать dict на основе ключей:

# 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.
• использовать алгоритм поиска, например двоичный поиск.

OR

Вы можете получить доступ к любому ключу случайным образом, используя этот синтаксис inven[key_calculator('Orange')].