Как оптимально искать в большом массиве?

Question

[artstylee]

[
   {
       "start": "2023-01-19T04:10:10:000Z",
       "end": "2023-01-19T04:20:00:000Z"
   },
   ..., //similar object
   ..., //similar object
]

есть такой массив из 1000 объектов
и есть искомая дата в ISO "2023-01-19T04:10:10:000Z"
даты в массиве идут по порядку
мне нужно найти объект start/end или между совпадает с искомой датой
итерация через весь массив с преобразованием не оптимально
пришел к выводу что оптимальнее всего делить массив на два, проверять среднее значение(больше или меньше искомой даты) а потом делать тоже самое в одной половине массива и так по кругу пока не найду искомое значение.
уверен что я не первый кто с этим столкнулся. накидайте ссылок на пример решения такой задачи, не хочется изобретать велосипед

Answer 1

[Александр Талалаев]

Очевидный двоичный поиск. Рекурсивная функция, берёте элемент который по середине, сравниваете, отсекаете соответсвующую половину, и повторяете снова. В интернете полно примеров.

Comments

[twobomb]

Слишком банально и не интересно!
Если время между соседними элементами массива одинаковое, то можно довольно точно вычислить положение нужного, посмотрев на первый и конечный. Ну даже если разброс времени небольшой, можно более оптимизированно делить массив, чем просто по две части.
Ну на самом деле тут не нужен ни один из таких вариантов, можно тупо перебором делать тут же всего 1000 элементов. Если бы хотя бы миллион был...