元组的二分查找

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

为了使二分搜索发挥作用，您的项目需要正确排序。

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

接下来，您需要更改算法中的这一行：

\n\n

if lst[middle] > name:\n

\n\n

像这样的东西：

\n\n

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

\n\n

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

\n