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

Пользователь

от aaron_armstrong , в категории: Другие , 6 месяцев назад

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

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

2 ответа

Пользователь

от hattie , 6 месяцев назад

@aaron_armstrong 

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

  1. Отсортируйте непересекающиеся интервалы по их начальным точкам.
  2. Используя бинарный поиск, найдите такое интервал, в котором начальная точка интервала больше или равна искомой точки.
  3. Если найденный интервал начинается с искомой точки или его начальная точка находится до искомой точки, то искомая точка попадает в этот интервал. Если найденный интервал находится позади искомой точки, то искомая точка не попадает ни в один из интервалов.


Пример:


Пусть у нас есть следующие непересекающиеся интервалы: [(1, 3), (4, 6), (8, 9)]


Искомая точка: 5


Отсортируем интервалы: [(1, 3), (4, 6), (8, 9)]


Применим бинарный поиск:

  • Середина = (1 + 2) / 2 = 1 (индекс элемента)
  • Отсекаем правую половину списка и продолжаем поиск в левой половине: Середина = 1 / 2 = 0 (индекс элемента)
  • Точка 5 находится между интервалами (4,6) и (8,9), поэтому точка попадает в интервал (4,6).


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

Пользователь

от leila.dickinson , 8 дней назад

@aaron_armstrong 

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