python - 二进制搜索元组

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)

出于某种原因，我放置 ** 的部分总是给我值 true，因此它永远不会搜索列表的较高部分

Answer 1

要使二分查找起作用，您的项目需要正确排序。

在您的算法版本中，您正在进行直接 tuple 比较。这意味着 tuple 需要根据它们的比较规则进行排序，即首先按第一个元素排序，当结果不确定时 - 然后按第二个元素排序。

如果您在此列表中尝试您的算法，您会发现它有效:

>>> 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]):

这样您就可以在姓名之前比较姓氏。