Почему мы пишем lo + (hi-lo)/2 в бинарном поиске?
Я читал о бинарном поиске... Я знаю, что традиционный способ нахождения среднего значения похож на
mid=(hi+lo)/2
Но я также вижу, что во избежание переполнения среднее значение вычисляется так, как
mid=lo+(hi-lo)/2
Но почему? Я не мог найти настоящую причину. Может ли кто-нибудь объяснить мне причину с примером?
Это отличается от другого вопроса, потому что у других вопросов не было ответа, который я хотел с примером...
Ответы
Ответ 1
Предположим, что вы ищете массив из 4000000000 элементов, используя 32-разрядные unsigned int в качестве индексов.
Первый шаг заставил его выглядеть так, как будто искомый элемент, если он присутствует, будет в верхней половине. lo значение 2000000000 и hi равно 4000000000.
hi + lo переполняет и производит значение, меньшее, чем предполагаемое 6000000000. Он фактически производит 6000000000-2 32. В результате (hi + lo) / 2 является небольшим значением. Это даже не между lo и hi!
С этого момента поиск будет неправильным (вероятно, он заключит, что элемент отсутствует, даже если он был там).
В отличие от этого, даже с экстремальными значениями в этом примере, lo + (hi - lo) / 2 всегда вычисляет индекс на полпути между hi и lo, как это предусмотрено алгоритмом.
Ответ 2
Математически говоря, они эквивалентны.
В терминах компьютера mid=(hi+lo)/2 выполняется меньше операций, но mid=lo+(hi-lo)/2 является предпочтительным, чтобы избежать переполнения.
Скажем, что элемент, который вы ищете, находится ближе к концу массива, тогда hi+lo почти 2*size. Поскольку size может быть почти таким же большим, как ваш максимальный индекс, 2*size и, следовательно, hi+lo может переполняться.
