如何对相同值的范围进行二进制搜索? [英] How to do a binary search for a range of the same value?

问题描述

我有一个排序的数字列表，我需要让它返回该数字出现的索引范围.我的清单是:

I have a sorted list of numbers and I need to get it return the range of index that the number appears. My list is:

daysSick = [0, 0, 0, 0, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 11, 15, 24]

如果我搜索0，则需要返回(0，3).现在，我只能找到一个数字的位置！我知道如何执行二进制搜索，但是我仍然被困在如何使它从该位置上下移动以找到其他相同值的过程中！

If I searched 0, I need to return (0, 3). Right now I can only get it to find the spot of one number! I know how to do the binary search, but I am stuck how to make it move up and down from the position to find the other same values!

low = 0
high = len(daysSick) - 1
while low <= high :
    mid = (low + high) // 2
    if value < daysSick[mid]:
        high = mid - 1
    elif value > list[mid]:
        low = mid + 1
    else:
        return mid

推荐答案

我提出的解决方案比

I present a solution faster than the raw functions taken from the bisect library

具有优化二进制搜索

def search(a, x):
    right = 0
    h = len(a)
    while right < h:
        m = (right+h)//2
        if x < a[m]: h = m
        else: 
            right = m+1
    # start binary search for left element only 
    # including elements from 0 to right-1 - much faster!
    left = 0
    h = right - 1
    while left < h:
        m = (left+h)//2
        if x > a[m]: left = m+1
        else: 
            h = m
    return left, right-1

search(daysSick, 5)
(10, 12)

search(daysSick, 2)
(5, 5)

比较与Bisect

• 使用自定义二进制搜索...

  Comparision vs. Bisect

  • Using customised binary search...

    %timeit search(daysSick, 3)
    1000000 loops, best of 3: 1.23 µs per loop
    

  • 将源代码中的原始代码从bisect复制到python ...

  • Copying the raw code from the source from bisect into python...

    %timeit bisect_left(daysSick, 1), bisect_right(daysSick, 1)
    1000000 loops, best of 3: 1.77 µs per loop
    

  • 使用默认导入到目前为止是最快的，因为我认为它可能会在幕后进行优化...

  • Using default import is by far the fastest as I think it might be optimised behind the scenes ...

    from bisect import bisect_left, bisect_right
    %timeit bisect_left(daysSick, 1), bisect_right(daysSick, 1)
    1000000 loops, best of 3: 504 ns per loop
    

  没有分机号.库，但不是二进制搜索

  Without ext. libraries but not binary search

  daysSick = [0, 0, 0, 0, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 11, 15, 24]
  
  # using a function
  idxL = lambda val, lst:  [i for i,d in enumerate(lst) if d==val]
  
  allVals = idxL(0,daysSick)
  (0, 3)
  

  这篇关于如何对相同值的范围进行二进制搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！