Есть ли более быстрый способ поиска, находится ли значение в пределах интервала, учитывая список интервалов?

Question

Как часть моего кода, у меня есть следующая проблема: У меня есть следующие списки:

    intervals = [(1,3), (5,12), (16,20)]
    labels = [[1,2],[1],[2,3]]

Первый - это список отсортированных непересекающихся интервалов, а второй - «разрешенные» метки соответствующего интервала. Например, метки 1 и 2 допускаются в интервале (1,3). Также интервалы имеют вид [а, б).

Я хочу найти, если для кортежа (t, l):

1. t находится в пределах интервала между списками.
2. l разрешено в этом интервале.

Подход, который я мог бы придумать, - разбить список интервалов на минимумы и максимумы:

    lows = np.array([1,5,16])
    highs = np.array([3,12,20])
    find_indx = np.where(lows >= t)
    if len(find_indx[0]) > 0:
         indx = find_indx[0][0]
         if t < highs[low_indx] and l in labels[low_indx]:
              return 'Yes'
    return 'No'

Есть ли более быстрый / чистый подход к этой проблеме? Разве быстрее использовать бинарный поиск, чем встроенную функцию python?

Answer 1

Вы можете реализовать бинарный поиск в начальных интервалах, чтобы уменьшить временную сложность каждого поиска до записи (N). Например, пусть

label = [10,11]
intervals = [(1,3), (5,12), (16,20)]

Поскольку интервалы не перекрываются, нам нужно найти начало первого интервала меньше или равным началу метки.

    int val = 10;
    int arr[] = {1,5,16};

    int low = 0;
    int high = arr.length-1;

    while(high>=low)
    {
        int mid = low + (high-low)/2;
        if(arr[mid] == val)
            return arr[mid];
        else if(high == arr.length-1 && arr[mid]<val)
            return arr[high];
        else if(low == 0 && arr[mid]>val)
            return arr[low];
        else if(arr[mid]>val)
            high = mid-1;
        else
            low = mid+1;
    }

    System.out.println(arr[low]);

Здесь вывод будет 5. Теперь мы можем легко проверить, принадлежит ли данный ярлык этому интервалу или нет.