Я видел, как программисты использовали формулу

mid = start + (end - start) / 2

вместо использования более простой формулы

mid = (start + end) / 2

для поиска среднего элемента в массиве или списке.

Почему они используют первый?

Pallavi Chauhan

Ответов: 4

Ответы (4)

Мы можем проиллюстрировать этот факт на простом примере. Допустим, в некотором массиве large мы пытаемся найти середину диапазона [1000, INT_MAX]. Теперь INT_MAX - это наибольшее значение, которое может хранить тип данных int. Даже если к этому добавить 1, окончательное значение станет отрицательным.

Также, start = 1000 и end = INT_MAX.

По формуле: (начало + конец) / 2,

средняя точка будет

(1000 + INT_MAX) / 2 = - (INT_MAX + 999) / 2, что равно отрицательно и может привести к ошибке сегментации, если мы попытаемся проиндексировать с использованием этого значения.

Но, используя формулу (start + (end-start) / 2), получаем:

(1000 + (INT_MAX-1000) / 2) = (1000 + INT_MAX / 2 - 500) = (INT_MAX / 2 + 500)который не переполнится.

Есть три причины.

Прежде всего, start + (end - start) / 2 работает, даже если вы используете указатели, пока end - start не переполняется1.

int *start = ..., *end = ...;
int *mid = start + (end - start) / 2; // works as expected
int *mid = (start + end) / 2;         // type error, won't compile

Во-вторых, start + (end - start) / 2 не переполняется, если start и end - большие положительные числа. Для операндов со знаком переполнение не определено:

int start = 0x7ffffffe, end = 0x7fffffff;
int mid = start + (end - start) / 2; // works as expected
int mid = (start + end) / 2;         // overflow... undefined

(Обратите внимание, что end - start может переполняться, но только если start <0 или end <0.)

Или при беззнаковой арифметике переполнение определяется, но дает неправильный ответ. Однако для беззнаковых операндов start + (end - start) / 2 никогда не переполнится, пока end> ​​= start.

unsigned start = 0xfffffffeu, end = 0xffffffffu;
unsigned mid = start + (end - start) / 2; // works as expected
unsigned mid = (start + end) / 2;         // mid = 0x7ffffffe

Наконец, вы часто хотите округлить до элемента start.

int start = -3, end = 0;
int mid = start + (end - start) / 2; // -2, closer to start
int mid = (start + end) / 2;         // -1, surprise!

Сноски

1 Согласно стандарту C, если результат вычитания указателя не может быть представлен как ptrdiff_t, то поведение не определено. Однако на практике для этого требуется выделить массив char, используя как минимум половину всего адресного пространства.

В дополнение к тому, что уже сказали другие, первый объясняет его значение яснее для тех, кто менее математически настроен:

mid = start + (end - start) / 2

читается как

середина равна началу плюс половина длины.

тогда как:

mid = (start + end) / 2

читается как

середина равна половине начала плюс конец

Что не кажется таким ясным, как первое, по крайней мере, если так выразиться.

, как указал Кос, это также может читаться:

mid равняется среднему значению начала и конца

Что яснее, но все же, по крайней мере, на мой взгляд, не так ясно, как первое.

start + (end-start) / 2 может избежать возможного переполнения, например start = 2 ^ 20 и end = 2 ^ 30

2022 WebDevInsider