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

Question

Challenge: I would like to find when logic changes from HIGH(1) to LOW (0) and vice versa.

Numeric examples:

1. Swiping data 0 to 5 with step of 0.05 the logic changes from LOW(0) to HIGH (1) when input value = 3.5.

• arr = [0, 0.05..3.5..5]
• When value in arr = 3.5. The state changes to HIGH(1)

2. Swiping data 5 to 0 with step of 0.05 the logic changes from HIGH (1) to LOW(0) when input value = 2.5.

• arr = [5, 4.95..2.5..0]
• When value in arr = 2.5. The state changes to LOW(0)

Below is my functional code:

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

Need help with:

One of my colleague mentioned it could be done with a binary search I have tried to integrate it into my code but miserably failed... If anyone knows, if it is even possible to use the binary search in this code or there is a more efficient way of doing it, please let me know.

Answer 1

Because your array is sorted you using binary search allow to pass from average O(n) to O(log(n)) which can be dramatic on large datasets.

You have to customize the binary search because you do not search an exact value.

For example you may do something like this:

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