带in的二进制搜索算法

Question

我试图更改我的代码，这样就不会找到数组的特定值，而是输出一个间隔的值，例如60-70。感谢任何帮助。在

def binary (array, value):

    while len(array)!= 0:
        mid = len(array) // 2

        if value == array[mid]:           
            return value
        elif value > array[mid]:       
            array = array[mid+1:]
        elif value < array [mid]:          
            array = array[0:mid]

sequence = [1,2,5,9,13,42,69,123,256]

print( "found", binary(sequence,70) ) 

到目前为止，我有这个，希望它找到一个指定的间隔，所以如果我指定60-70，它会找到介于两者之间的时间。在

Answer 1

其实这很简单：
在搜索间隔(lower, upper)中的元素时，对数组arr执行二进制搜索，查找最小元素arr[n]的索引，这样arr[n] >= lower和最大元素的索引{}，这样arr[m] <= upper。在

现在有几种可能性：

• n<；m:阵列中存在多个解决方案。所有的都在从索引n开始到索引m的子数组中
• n=m：只存在一个解：arr[n]
• n>；m:没有解决方案

可以使用如下的二进制搜索来搜索超过某个阈值的值：

def lowestGreaterThan(arr, threshold):
    low = 0
    high = len(arr)

    while low < high:
        mid = math.floor((low + high) / 2)

        print("low = ", low, " mid = ", mid, " high = ", high)

        if arr[mid] == threshold:
            return mid
        elif arr[mid] < threshold and mid != low:
            low = mid
        elif arr[mid] > threshold and mid != high:
            high = mid
        else:
            # terminate with index pointing to the first element greater than low
            high = low = low + 1

    return low

对于代码的外观很抱歉，我的python远远不够完美。不管怎样，这应该显示出该方法背后的基本思想。该算法基本上搜索具有属性arr[ind] >= threshold的数组中第一个元素的索引ind。在