多值的二进制搜索

Question

嗨，我有一个与python有关的问题

我有一个排序的Numpy数组，我必须快速找到某些值的索引，到目前为止我一直在使用二进制搜索，但问题是有很多相同值的条目，我必须找到所有值的索引。有没有办法修改二进制搜索来找到全部？
当前代码为

def binarySearch(alist,item,con_array,element):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:            
            for l in range(len(alist)):
                if alist[l] == item:
                    n_array.append(con_array[l])
            return True                   
        else:
            if item<alist[midpoint]:
                return binarySearch(alist[:midpoint],item,con_array[:midpoint],i)
            else:
                return binarySearch(alist[midpoint+1:],item,con_array[midpoint+1:],i) 

如您所见，我试图通过简单地搜索缩短的数组来合并它，但这仍然会删除一些值

Answer 1

二进制搜索可以很容易地适应于查找大于键的第一个值，因此通过两次搜索，您可以找到与键相等的值范围。NumPy实际上已经为您实现了：

>>> a = np.array([0, 1, 2, 2, 2, 3, 5, 7])
>>> left = np.searchsorted(a, 2, side='left')
>>> right = np.searchsorted(a, 2, side='right')
>>> a[left:right]
array([2, 2, 2])

对于非常大的数组，在a[left:]上执行第二次搜索可能会更有效：

^{pr2}$

Answer 2

采用二进制搜索来实现这一点是非常有教育意义的，当我教授算法时，我总是建议我的学生尝试一下。如果您只想完成它，numpy已经有一个函数可以执行您想要的操作：

import numpy as np
a = np.array([1,2,3,1,2,3,1,1])
np.where(a==1)

哪些输出

^{pr2}$