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

160

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?

Pallavi Chauhan
źródło
51
Dzikie przypuszczenie: (start + end)może się przepełnić, ale (end - start)nie może.
cadaniluk
30
ponieważ ostatni nie działa, kiedy starti endsą wskaźnikami.
ensc
20
start + (end - start) / 2niesie również semantyczne znaczenie: (end - start)jest to długość, więc to mówi: start + half the length.
njzk2
2
@ LưuVĩnhPhúc: Czy to pytanie nie ma najlepszych odpowiedzi i największej liczby głosów? Jeśli tak, pozostałe pytania powinny zostać prawdopodobnie zamknięte jako dupek tego pytania. Wiek postów nie ma znaczenia.
Nisse Engström

Odpowiedzi:

218

Są trzy powody.

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

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

1 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.

Dietrich Epp
źródło
wynikać z (end - start)w signed intprzypadek jest niezdefiniowana, kiedy przelewa.
ensc
Czy możesz udowodnić, że się end-startnie przepełni? AFAIK, jeśli weźmiesz negatyw start, powinno być możliwe, aby się przepełnił. Jasne, w większości przypadków, gdy >= 0
obliczasz
12
@Bakuriu: Nie da się udowodnić czegoś, co nie jest prawdą.
Dietrich Epp
4
Jest szczególnie interesujący w C, ponieważ odejmowanie wskaźnika (zgodnie ze standardem) jest z założenia łamane. Implementacje mogą tworzyć tablice tak duże, że end - startjest niezdefiniowane, ponieważ rozmiary obiektów są niepodpisane, a różnice wskaźników są podpisane. Więc end - start„działa nawet przy użyciu wskaźników”, pod warunkiem, że w jakiś sposób zachowasz rozmiar tablicy poniżej PTRDIFF_MAX. Aby być uczciwym w stosunku do standardu, nie jest to duża przeszkoda w przypadku większości architektur, ponieważ jest to połowa rozmiaru mapy pamięci.
Steve Jessop
3
@Bakuriu: Nawiasem mówiąc, w poście znajduje się przycisk „edytuj”, którego możesz użyć, aby zasugerować zmiany (lub wprowadzić je samodzielnie), jeśli uważasz, że coś przeoczyłem lub coś jest niejasne. Jestem tylko człowiekiem, a ten wpis obejrzało ponad dwa tysiące par gałek ocznych. Ten rodzaj komentarza, „Powinieneś wyjaśnić…”, naprawdę mnie denerwuje.
Dietrich Epp
18

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 .

Shubham
źródło
1
Jeśli dodasz 1 do INT_MAX, wynik nie będzie ujemny, ale niezdefiniowany.
celtschk
@celtschk Teoretycznie tak. Praktycznie będzie zawijał się w wielu przypadkach od INT_MAXdo -INT_MAX. Jednak poleganie na tym jest złym nawykiem.
Maszt
17

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.

TheLethalCoder
źródło
3
Rozumiem twój punkt widzenia, ale to naprawdę jest naciągane. Jeśli widzisz „e - s” i myślisz „długość”, to prawie na pewno widzisz „(s + e) ​​/ 2” i myślisz „średnio” lub „średnio”.
djechlin
2
@djechlin Programiści są słabi z matematyki. Są zajęci swoją pracą. Nie mają czasu na zajęcia z matematyki.
Little Alien
1

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

fight_club
źródło