时间戳

首页 > 解决方案 > 如何在 Python 中使用二分搜索查找多个值

python - 如何在 Python 中使用二分搜索查找多个值

问题描述

我正在使用标准的二进制搜索算法，该算法将整数值作为参数，并在列表中搜索整数。但是，我希望能够找到列表中与搜索值匹配的每个整数的位置索引。到目前为止，我所拥有的是：

def bin_search(x):
    my_list = [57,68,76,77,82,86,89,89,89,98,100]
    bottom = 0
    top = len(my_list)-1
    found = False
    location = -1
    while(bottom <= top) and not(found):
        middle = int((bottom + top)//2)
        if(my_list[middle] == x):
            location = middle
            found = True
        else:
            if x < my_list[middle]:
                top = middle - 1
            else:
                bottom = middle + 1

    return location

print(bin_search(89))

任何帮助使这个二进制搜索能够找到两个值将不胜感激！

标签： pythonbinary-search

解决方案

在二进制搜索的末尾添加此代码将为用户提供正在搜索的值的第一次和最后一次出现的索引（在本例中为 x）。然后，用户可以使用索引来查找与搜索项匹配的索引范围，因为他们知道搜索项的第一次和最后一次出现的索引。

# Index of last occurrence
location2 = -1
# Index of first occurrence
location3 = -1

# Finds last index that matches x
for I in range(len(my_list)):
    if my_list[I] == x:
        location2 = I
# Finds first index that matches x
for I in range(len(my_list)):
    if my_list[I] == x:
        location3 = I
        break

推荐阅读