为什么我无法使用二进制搜索从列表中获取最后一个数字？

Question

我已经编写了一个代码来查找用户要求的数字的索引位置。除最后一个数字（在对列表进行排序之后）以外，在这种情况下为92，以下是代码，我将获得所有数字的答案。请指导这里有什么问题。

# Python program to implement binary search

list = [54, 67, 85, 33, 92, 74]
list.sort()
print(f'Given list is: {list}')

low = 0
upp = len(list)-1
mid = (low + upp) // 2

num = list.index(int(input('Enter number: ')))

while num != mid:
    mid = (low + upp) // 2
    if num < mid:
        upp = mid
        mid = (low + upp) // 2
    else:
        if num > mid:
            low = mid
            mid = (low + upp) // 2
print(f'found at {mid} index')

Answer 1

您所描述的问题是，您使用的算法旨在将 upp 作为 exclusive 上限；通过将其初始化为 len（list）-1 ，您根本找不到最上面的索引。更改 upp = len（list）-1 to upp = len（list）和代码“ works”（它没有做任何有用的事情）。

您的其他问题是：

1. num = list.index（int（intpation（'enter number：'）））直接使您获得索引，并使用 o（o（n））搜索在引擎盖下，消除了二进制搜索的好处。您的其余代码甚至都不查看您的 list ，您只是在做 o（log n）工作以查找 MID 等于 num ，当 mid = num 将达到相同的结果时，不涉及搜索（no 附加搜索超出 list.index 无论如何都在做）。
2. 您命名了变量 list ，这意味着 list 构造函数不可用；这是一个坏主意（即使在这里没有破坏任何东西）。
3. （当前代码中不是问题，而是试图修复＃1的问题）当搜索值搜索的值不在 list list （在您的当前代码中，<代码> list.index 通过提高异常来调用该处理，但是如前所述，如果您使用 list.index ，您将完全无法从二进制搜索中受益）。

对于＃1，您想接受没有 list.index 的输入：

num = int(input('Enter number: '))

然后更改 num 和 MID 之间的每个比较以比较 num 和 list [mid] （或 myList [mid] 或您用于 list> List ）的任何更好的名称），所以 num 始终是搜索 value ，中间是当前索引正在搜索， list [mid] 是该索引的价值。您还需要改进搜索，因此当您要搜索的值中不存在 list （作为练习;在伪代码和Python中，在那里），而不是永远循环。

Answer 2

这是一个二进制搜索实现，可以帮助您查看自己出了问题的位置：

list_ = sorted([54, 67, 85, 33, 92, 74])

def bsearch(lst, x):
    L = 0
    R = len(lst) - 1
    while L <= R:
        m = (L + R) // 2
        if (v := lst[m]) == x:
            return m
        if v < x:
            L = m + 1
        else:
            R = m - 1
    return -1

while (x := input('Enter a number to search for (q to quit): ')) not in 'Qq':
    try:
        if (i := bsearch(list_, int(x))) < 0:
            print('Not found')
        else:
            print(f'Found at {i}')
    except ValueError as e:
        print(e)