Как быстро найти в какой из непересекающихся интервалов попадает точка?

Накатал на скорую руку обычный двоичный поиск.

Для начала надо как то сравнивать точку и интервал

private int Compare(int point, int[] interval)
{
    if (point < interval[0]) return -1;
    if (point >= interval[1]) return 1;
    return 0;
}

Потом реализовать простейший двоичный поиск

private int BinarySearch(int[][] data, int point)
{
    var l = 0;
    var r = data.Length - 1;

    while (r >= l)
    {
        var mid = l + (r - l) / 2;
        var midCompare = Compare(point, data[mid]);
        if (midCompare == 0) return mid;
        if (midCompare < 0) r = mid - 1;
        else l = mid + 1;
    }

    return -1;
}

ну и проверка

var data = new[] {
        new []{0, 2},
        new []{2, 4},
        new []{5, 6},
        new []{17, 19},
        new []{21, 30},
        new []{32, 90},
        new []{96, 124},
        new []{125, 900},
    };

Console.WriteLine(BinarySearch(data, 25));
Console.WriteLine(BinarySearch(data, 20));

Вывод

4
-1

Сильно не дебажил код, но идея думаю ясна.

Конечно, двоичный поиск - это общий алгоритм, который к сортированным данным легко применить. Однако, он может оказаться не самым эффективным, если пытаться учитывть какие то конкретные особенности ваших данных и вариантов использования вашего алгоритма.

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

var data = new[] {
    new []{0, 2},
    new []{2, 4},
    new []{5, 6},
    new []{17, 19},
    new []{21, 30},
    new []{32, 90},
    new []{96, 124},
    new []{125, 900},
};

var points = Enumerable.Repeat(-1, 1000).ToArray(); 
for(int i=0; i<data.Length; i++)
    for (int j = data[i][0]; j < data[i][1]; j++)
        points[j] = i;

Console.WriteLine(points[25]);
Console.WriteLine(points[20]);

Выисление индекса в этом случае тривиальное и очень быстрое. Однако, на таких числах (1000 точек) на практике алгоритм покажет прирост скорости если количество вызовов кода будет большим. Условно, если у вас N точек в интервале, подготовка варианта с массивом займет N и поиск будет константой, при этом двоичный поиск будет Log(N), вроде очевидно, что N+1>log(N) (при N=1000 это будет 1001 > 10, то есть бинарный поиск в 10 раз быстрее). Добавим количество запросов сюда, получим

N + 1*K = K*Log(N)

Чтобы понять, со скольки запросов массив будет обгонять двоичный поиск, решим уравнение

K = N / (Log(N) - 1)

N=1000, то получаем примерно K=10. Конечно, это очень неточно, прямо скажем, сильно очень не точно, но я надеюсь, идея понятная - количество запорсов должно линейно расти (или быстрее, чем линейно) от количества точек, чтобы алгоритм с массивом оставался эффективным. Вот как выглядит зависимость

То есть, условно, на массиве из 40000 точек надо выполнить как минимум 3000-4000 тысячи запросов, чтобы оправдать время построения массива перед обычным довичным поиском.

Другой вариант данных - это когда у вас нет четкого интервала всех точек, но у вас много малентких интервальчиков, все точки которых в сумме влезают в интервал, например, тот же 1000. То есть у вас могут быть [0, 5), [5000, 5007), [10000, 100010) и так далее, но в сумме у вас точек все равно не более 1000, условно. Тогда можно от массива перейти к хештаблице (он же словарь). Пример:

Получение значения из словаря

private int GetOrDefault(Dictionary<int, int> data, int key, int def)
{
    if (data.ContainsKey(key)) return data[key];
    return def;
}

тест

var data = new[] {
    new []{0, 2},
    new []{2, 4},
    new []{5, 6},
    new []{17, 19},
    new []{21, 30},
    new []{32, 90},
    new []{96, 124},
    new []{125, 900},
};

var points = new Dictionary<int, int>();
for (int i = 0; i < data.Length; i++)
    for (int j = data[i][0]; j < data[i][1]; j++)
        points[j] = i;


Console.WriteLine(GetOrDefault(points, 25, -1));
Console.WriteLine(GetOrDefault(points, 20, -1));

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

Поместите все концы всех отрезков в единый массив. В этом массиве выполните обычный двоичный поиск, который возвращает индекс для вставки значения. Для 20 индекс равен 8 (если 20 вставить между элементами с индексами 8 и 9, порядок сохранится). Для 25 индекс равен 9:

                             25
                             |
                             v
[0, 2, 2, 4, 5, 6, 17, 19, 21, 30, 32, 90, 96, 124, 125, 900]
                         ^
                         |
                         20

Если индекс (i) вставки нечётный, то точка попала в отрезок с индексом (i - 1) / 2. Иначе точка попала в промежуток между отрезками.

bsearch(a, x) возвращает индекс для вставки x в массив a:

• 0 если x < a[0],
• len(a) если a[len(a) - 1] <= x,
• иначе i такой что a[i - 1] <= x < a[i].

where(points, x) возвращает индекс отрезка в который попал x если он попал. Если x никуда не попал со знаком минус возвращается индекс отрезка следующего за x.

def bsearch(a, x):
    lo = 0
    hi = len(a) - 1

    if x < a[lo]:
        return 0

    if a[hi] <= x:
        return len(a)

    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid

    return hi


def where(points, x):
    i = bsearch(points, x)
    if i % 2 == 0:
        return -(i // 2) - 1
    return i // 2

    
segments = [
    (0, 2),
    (2, 4),
    (5, 6),
    (17, 19),
    (21, 30),
    (32, 90),
    (96, 124),
    (125, 900)
]

points = [p for s in segments for p in s]
for x in (-1, 0, 1, 2, 3, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 899, 900, 901):
    w = where(points, x)
    print(w, end=': ')
    if w < 0:
        i = -w - 1
        if 0 < i:
            print(f'[{segments[i - 1][0]}, {segments[i - 1][1]}) < ', end='')
        print(x, end='')
        if i < len(segments):
            print(f' < [{segments[i][0]}, {segments[i][1]})', end='')
        print()
    else:
        i = w
        print(f'[{segments[i][0]} <= {x} < {segments[i][1]})')

Если x попал в отрезок печатается в какой отрезок он попал. Иначе печатаются отрезки между которыми он попал:

-1: -1 < [0, 2)
0: [0 <= 0 < 2)
0: [0 <= 1 < 2)
1: [2 <= 2 < 4)
1: [2 <= 3 < 4)
-3: [2, 4) < 4 < [5, 6)
2: [5 <= 5 < 6)
-4: [5, 6) < 6 < [17, 19)
-4: [5, 6) < 7 < [17, 19)
-4: [5, 6) < 16 < [17, 19)
3: [17 <= 17 < 19)
3: [17 <= 18 < 19)
-5: [17, 19) < 19 < [21, 30)
-5: [17, 19) < 20 < [21, 30)
4: [21 <= 21 < 30)
4: [21 <= 22 < 30)
7: [125 <= 899 < 900)
-9: [125, 900) < 900
-9: [125, 900) < 901