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

要使二分搜索正常工作，您的项目需要正确排序。

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

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

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

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