在python中查找从低到高的状态转换(使用二进制搜索)

Question

挑战：I想知道逻辑何时从高(1)变为低(0)，反之亦然。

​

​

数字示例：

1. 当输入值= 3.5时，逻辑从低(0)到高(1)。

• arr = 0，0.05.3.5.5
• 当arr = 3.5时。状态变化为高(1)

1. 当输入值= 2.5时，逻辑从高(1)到低(0)。

• arr = 5，4.95.2.5.0
• 以arr = 2.5为单位。状态更改为低(0)

下面是我的函数代码：

def get_state(value):
    if value > 3.5:
        return 1
    if value < 2.5:
        return 0

def find_state_changed(arr):
    low_state = get_state(min(arr))
    high_state = get_state(max(arr))
    for up in arr:
        if get_state(up) != low_state:
            LowHigh = up
            break
        
    for low in arr[::-1]:
        if get_state(low) != high_state:
            HighLow = low
            break
    return LowHigh, HighLow

low = 0
high = 5
iteration = 100
step = (high - low)/iteration

arr = [round(i * step,2) for i in list(range(iteration+1))]
print(find_state_changed(arr))

需要帮助：

我的一位同事提到可以用二进制搜索来完成它，我已经尝试将它集成到我的代码中，但不幸的是失败了.如果有人知道，如果有可能在这段代码中使用二进制搜索，或者有一种更有效的方法，请告诉我。

Answer 1

由于您的数组是排序的，所以使用二进制搜索允许从平均O(n)传递到O(log(n))，这在大型数据集上可能是引人注目的。

您必须自定义二进制搜索，因为您没有搜索确切的值。

例如，您可以这样做：

def custom_binary_search(arr, value):
    """
    return the position of value in arr if value in arr. Alse return the position of the nearest superior value.
    :param arr:
    :param value:
    :return:
    """
    _arr = arr[::]
    left_ = 0
    right_ = len(arr) - 1
    while True:  # possible infinite loops here
        middle_i = int((right_ - left_) / 2)
        middle_v = arr[middle_i]
        if middle_v == value:
            return middle_i
        elif middle_v < value and arr[middle_i + 1] > value:
            return middle_i + 1
        elif middle_v < value:
            right_ = middle_i
        elif middle_v > value:
            left_ = middle_i
        else:
            raise AssertionError("Should never reach this condition")