python - 如何实现二进制搜索以查找字典列表中的项目的索引

Question

我有一个包含字典的列表：

base = [
    {"name": "Earth", "Density": 5.427},
    {"name": "Mars", "Density": 5.513},
    {"name": "Venus", "Density": 5.204},
]
name = input("What planet are you looking for? ")

该函数应返回项目（在本例中为行星）的索引，如果不存在则返回 -1。

F.e | For input= Earth, expected output would be: 0
For input = venus, expected output: 2

这binary search是这项任务的必备条件。我什至没有给你我的代码，因为它甚至不起作用。我知道二进制搜索是如何工作的，但不知道如何在字典列表中使用它。PS。您不必编写整个代码，只需帮助我如何在字典列表中实现二元搜索。

标签： pythonpython-3.xdictionarybinary-search

Answer 1

对于二进制搜索的每次迭代，它只是将您需要检查的项目数量减半，因此您是遍历树还是搜索列表并不重要。

如果要搜索的数据是简单整数、字典或复杂对象的列表，则无关紧要 - 如果您需要为下一个二进制印章选择“左”或“右”部分，则比较函数的工作是.

在您的情况下，您将找到数组的中间索引，在该位置获取字典并将 name 属性与您要查找的内容进行比较。如果项目不匹配，则使用递归将列表的左半部分或右半部分传递给相同的搜索函数。

这是递归二进制搜索算法的实现。