在 python 中查找从低到高的状态转换（使用二分查找）

Question

挑战： 我想知道逻辑何时从 HIGH(1) 变为 LOW (0)，反之亦然。

数值示例：

当输入值 = 3.5 时，以 0.05 的步长将数据 0 滑动到 5，逻辑从 LOW(0) 变为 HIGH(1)。

arr = [0, 0.05..3.5..5]
当 arr 中的值 = 3.5 时。状态变为 HIGH(1)

当输入值 = 2.5 时，以 0.05 的步长将数据 5 滑动到 0，逻辑从高电平 (1) 变为低电平 (0)。

arr = [5, 4.95..2.5..0]
当 arr 中的值 = 2.5 时。状态变为 LOW(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))

需要帮助：

我的一位同事提到它可以用 binary search 来完成我试图将它集成到我的代码中但不幸地失败了...... 如果有人知道，如果甚至可以在此代码中使用二进制搜索或者有更有效的方法，请告诉我。

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")

在 python 中查找从低到高的状态转换（使用二分查找）

Find state transition from Low to High in python (using binary search)

python

binary-search

python-3.x