二进制搜索元组

Question

我正在尝试制作一个使用二进制搜索的代码，以将元组与其中的2个值进行比较（名称，姓氏）

names = [('Josh', 'Belluga'), ('Daisy', 'Fox'), ('Elin', 'Grosefield'), ('Dina', 'Ram'), ('Mike', 'Levinsan')]

二进制搜索代码获取该排序列表

def find_name(lst,name,low,high):
    if name == lst[high]:
        return high
    if name == lst[low]:
        return low
    if low >= high:
        return None
    middle = (low + high) / 2
    if lst[middle] == name:
        return middle
    **if lst[middle] > name:**
        return find_name(lst, name, low, middle)
    return find_name(lst, name, middle + 1,high)

出于某种原因，我将**始终给我的价值真实的部分，因此它永远不会搜索列表的更高部分

Answer 1

用于二进制搜索以工作，您的项目需要正确排序。

在您的算法版本中，您正在执行直接的tuple比较。这意味着tuple s需要根据其比较规则进行排序，即首先是第一个元素，而当结果尚无定论时，则需要进行分类。

。

如果您在此列表上尝试了算法，则会看到它有效：

>>> list(sorted(names))
[('Daisy', 'Fox'), ('Dina', 'Ram'), ('Elin', 'Grosefield'), ('Josh', 'Belluga'), ('Mike', 'Levinsan')]

如果要按姓氏对列表进行排序，则首先需要将('Mike', 'Levinsan')放在正确的位置。结果应该是：

>>> list(sorted(names, key=lambda x: (x[1], x[0])))
[('Josh', 'Belluga'), ('Daisy', 'Fox'), ('Elin', 'Grosefield'), ('Mike', 'Levinsan'), ('Dina', 'Ram')]

接下来，您需要在算法中更改此行：

if lst[middle] > name:

类似：

if (lst[middle][1], lst[middle][0]) > (name[1], name[0]):

以便您要比较名称之前的姓氏。