Po co preferować początek + (koniec - początek) / 2 zamiast (początek + koniec) / 2 przy obliczaniu środka tablicy?

Widziałem programistów używających formuły

mid = start + (end - start) / 2

zamiast korzystać z prostszej formuły

mid = (start + end) / 2

do znajdowania środkowego elementu w tablicy lub na liście.

Dlaczego używają tego pierwszego?

Są trzy powody.

Przede wszystkim start + (end - start) / 2działa nawet jeśli używasz wskaźników, o ile end - startnie przepełnia ¹ .

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

Po drugie, start + (end - start) / 2nie przepełni, jeśli starti endsą dużymi liczbami dodatnimi. W przypadku operandów ze znakiem przepełnienie jest niezdefiniowane:

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

(Pamiętaj, że end - startmoże się przepełnić, ale tylko wtedy, gdy start < 0lub end < 0.)

Lub w przypadku arytmetyki bez znaku przepełnienie jest zdefiniowane, ale daje złą odpowiedź. Jednak w przypadku operandów bez znaku start + (end - start) / 2nigdy nie przepełni się tak długo, jak end >= start.

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

Wreszcie, często chcesz zaokrąglić w kierunku startelementu.

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

Przypisy

¹ Zgodnie ze standardem C, jeśli wynik odejmowania wskaźnika nie jest reprezentowalny jako a ptrdiff_t, to zachowanie jest niezdefiniowane. Jednak w praktyce wymaga to przydzielenia chartablicy zajmującej co najmniej połowę całej przestrzeni adresowej.

Aby to wykazać, możemy posłużyć się prostym przykładem. Załóżmy, że w pewnej dużej tablicy próbujemy znaleźć środek zakresu [1000, INT_MAX]. Teraz,INT_MAX jest największą wartością, jaką inttyp danych może przechowywać. Nawet jeśli 1zostanie do tego dodany, ostateczna wartość stanie się ujemna.

Również start = 1000i end = INT_MAX.

Za pomocą następującego wzoru: (start + end)/2,

punktem środkowym będzie

(1000 + INT_MAX)/2= -(INT_MAX+999)/2, co jest ujemne i może powodować błąd segmentacji, jeśli spróbujemy indeksować przy użyciu tej wartości.

Ale używając wzoru, (start + (end-start)/2)otrzymujemy:

(1000 + (INT_MAX-1000)/2)= (1000 + INT_MAX/2 - 500)= (INT_MAX/2 + 500) który się nie przepełni .

Aby dodać do tego, co powiedzieli inni, pierwszy z nich wyjaśnia jego znaczenie jaśniej dla tych, którzy są mniej matematyczni:

mid = start + (end - start) / 2

czyta jako:

środek to początek plus połowa długości.

natomiast:

mid = (start + end) / 2

czyta jako:

środek równa się połowie początku i końca

Co nie wydaje się tak jasne jak pierwsze, przynajmniej w ten sposób.

jak zaznaczył Kos, może też przeczytać:

mid jest średnią z początku i końca

Co jest jaśniejsze, ale nadal nie, przynajmniej moim zdaniem, tak jasne jak pierwsze.

start + (end-start) / 2 pozwala uniknąć możliwego przepełnienia, na przykład start = 2 ^ 20 i end = 2 ^ 30