У меня есть список массивов различного размера, каждый из которых представляет интервал, поддерживая минимальное и максимальное значения.Когда данные плотные, можно предположить, что минимальный интервал близок к максимальному предыдущему интервалу, но они никогда не перекрываются.
Я бы хотел определить, какому интервалу принадлежит точка, с как можно меньшим количеством сравнений.То, что я считаю наивным подходом, - это сначала снова сравнить мин, а идти влево меньше.В противном случае сравните с максимальным и идите направо, если оно больше, в противном случае мы нашли интервал.Мне интересно, могу ли я вместо этого сравнивать медиану каждого интервала и идти влево или вправо, не сравнивая сначала с минимальным и максимальным.Когда диапазон поиска становится равным 0, моя теория состоит в том, что я могу затем сравнить с минутой преемника, чтобы определить, какой интервал является правильным.Так что это похоже на стратегию активного ветвления, которая избегает двойного сравнения за интервал, но я не уверен, существует ли действующее готовое решение, которое работает.
Каков будет оптимальный алгоритм здесь?Я много читал о деревьях сегментов (что мне кажется наиболее близким к моей проблеме), но мне не удалось найти надежную ссылку для интеллектуального подхода двоичного поиска.
Интервалы не перекрываются, и список интервалов сортируется таким образом, чтобы интервал min был больше, чем максимум его предшественника.