Существует ли структура данных для поиска значений, соответствующих произвольным диапазонам?

Question

Для поиска на равенство ключей мы можем использовать тип данных, такой как hashmap, но существует ли структура данных для поиска значений, соответствующих произвольным диапазонам?

Приведенный ниже код Rust эмулирует это с помощью выражения match, но мне не нужно жестко кодировать случаи в коде.

let x = 5;

match x {
    d if d <= 0 => println!("d <= 0"),
    d if 1 < d && d <= 3 => println!("1 < d <= 3"),
    d if 4 < d && d <= 6 => println!("4 < d <= 6"),
    _ => {}
}

( Rust детская площадка )

Answer 1

Вы можете создать список диапазонов с начальными и конечными значениями. Сортировать этот список по начальному значению.

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

Если у вас относительно небольшой общий диапазон (скажем, целые числа от 1 до 1000), вы можете предварительно заполнить массив ссылок на диапазоны. Допустим, у вас есть 4 диапазона и возможные значения запроса от 0 до 10:

range1: 0, 2
range2: 3, 5
range3: 6, 8
range4: 7, 10

Тогда ваш массив будет [range1, range1, range1, range2, range2, range2, range3, range3, range3, range4, range4, range4, range4].

Вы можете расширить его до желаемого размера, в зависимости от того, сколько памяти вы хотите потратить. Это дает вам прямой поиск.