В разных источниках по бинарному поиску встретил две формулы поиска среднего элемента. Вроде результаты одинаковы. Вторая проще для запоминания и работы.
Какая из низ правильная и в чем особенности применения?
Вариант №1:
int middle = low + (high - low) / 2;
Вариант №2:
int middleIndex = (firstIndex + lastIndex) / 2;
Давайте исследуем формулы. Преобразуем первую формулу с учётом целочисленной арифметики. Умножим оба слагаемых на 4 - это не изменит их значение:
low + (high - low) / 2 = 4 * low / 4 + 2 * (high - low) / 4
= (4 * low + 2 * high - 2 * low) / 4 = (2 * high + 2 * low) / 4
= (low + high) / 2
Получается, формулы эквивалентны. Единственная разница между ними состоит в том, что первая никогда не вызовет переполнения при вычислении (при естественном условии low <= high), а вторая может вызвать.
Дело в том, что есть вероятность того, что сумма (firstIndex + lastIndex) может вызвать переполнение при значениях индексов, близких к Integer.MAX_VALUE (пример - сортировка одним из методов "разделяй и властвуй" или бинарный поиск по массиву байтов длиной 1200000000). А вариант с разностью, если параметры не перепутаны, от этого недостатка не страдает.
Данная проблема, например, рассматривается в книге Джона Бентли "Жемчужины программирования", где он указывает на неё как на типичную ошибку в реализации двоичного поиска, которая оставалась незамеченной десятки лет. Поскольку массивы редко бывают размером почти во всю доступную память, то в реальной работе встретить эту беду трудно. Но возможно.