时间戳

首页 > 解决方案 > 返回所有匹配值排序列表的索引

python - 返回所有匹配值排序列表的索引

问题描述

我最近在接受采访时遇到了这个问题，但一直无法解决。给定一个排序列表：

li = [1,2,2,3,4,4,4,4,5,5,5...]

返回与目标匹配的所有元素的索引，ex. 4时间复杂度为 O(log n)。

这个问题的设置向我表明这是一个二进制搜索问题。我用类似下面的东西回答了它，但还没有想出更好的东西：

data = [2,3,5,6,8,9,12,12,12,14,17,19,22,25,27,28,33,37]
target = 12

def binary_search(data, target):
    low = 0 
    high = len(data) - 1

    while low <= high:
        mid = (high + low) // 2
        if data[mid] == target:
            return mid
        elif data[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    
    return False

def return_other_indices(data, target, match_index):
    output = [match_index]

    i = match_index + 1
    while data[i] == target:
        output.append(i)
        i += 1

    i = match_index - 1
    while data[i] == target:
        output.append(i)
        i -= 1

    return output

match_index = binary_search(data, target)
output = return_other_indices(data, target, match_index)
print(output)

有没有更好的方法来做到这一点？

标签： pythonbinary-search

解决方案

我不确定这是否是您要寻找的，但这是使用 python 标准库的解决方案。

仅使用bisect：

from bisect import bisect_left, bisect
start = bisect_left(data, target)
stop = bisect(data, target, lo=start)
output = range(start, stop)
print(list(output))

输出：[6,7,8]

较旧的答案：

它bisect.bisect_left用于寻找起点，并itertools.takewhile获取所有元素。

from bisect import bisect_left
from itertools import takewhile, islice
left = bisect_left(data, target)
[left]+[i[0]+left+1 for i in takewhile(lambda x: x[1]==target,
                                       enumerate(islice(data, left+1, len(data))))]

注意。takewhile当预期只有几个目标并且数据很大时，线性版本可能会更快，否则双等分通常会更快

推荐阅读