Warum Start + (Ende - Start) / 2 gegenüber (Start + Ende) / 2 bevorzugen, wenn die Mitte eines Arrays berechnet wird?

Ich habe gesehen, wie Programmierer die Formel verwendet haben

mid = start + (end - start) / 2

anstatt die einfachere Formel zu verwenden

mid = (start + end) / 2

zum Finden des mittleren Elements im Array oder in der Liste.

Warum benutzen sie die erstere?

Es gibt drei Gründe.

Funktioniert zunächst start + (end - start) / 2einmal auch, wenn Sie Zeiger verwenden, solange end - startnicht ¹ überläuft .

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

Zweitens start + (end - start) / 2wird nicht überlaufen, wenn startund endsind große positive Zahlen. Bei signierten Operanden ist der Überlauf undefiniert:

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

(Beachten Sie, dass dies end - startüberlaufen kann, aber nur, wenn start < 0oder end < 0.)

Oder mit vorzeichenloser Arithmetik wird ein Überlauf definiert, der Ihnen jedoch die falsche Antwort gibt. Bei vorzeichenlosen Operanden start + (end - start) / 2wird jedoch niemals überlaufen, solange end >= start.

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

Schließlich möchten Sie häufig auf das startElement runden .

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

Fußnoten

¹ Nach dem C-Standard ist ptrdiff_tdas Verhalten undefiniert , wenn das Ergebnis der Zeigersubtraktion nicht als a dargestellt werden kann. In der Praxis erfordert dies jedoch die Zuweisung eines charArrays unter Verwendung mindestens der Hälfte des gesamten Adressraums.

Wir können ein einfaches Beispiel nehmen, um diese Tatsache zu demonstrieren. Angenommen, in einem bestimmten großen Array versuchen wir, den Mittelpunkt des Bereichs zu finden [1000, INT_MAX]. Jetzt INT_MAXist der größte Wert, den der intDatentyp speichern kann. Selbst wenn dies 1hinzugefügt wird, wird der Endwert negativ.

Auch start = 1000und end = INT_MAX.

Mit Hilfe der Formel: (start + end)/2,

der Mittelpunkt wird sein

(1000 + INT_MAX)/2= -(INT_MAX+999)/2, was negativ ist und einen Segmentierungsfehler verursachen kann, wenn wir versuchen, mit diesem Wert zu indizieren.

Aber mit der Formel erhalten (start + (end-start)/2)wir:

(1000 + (INT_MAX-1000)/2)= (1000 + INT_MAX/2 - 500)= (INT_MAX/2 + 500) was nicht überläuft .

Um das zu ergänzen, was andere bereits gesagt haben, erklärt der erste seinen weniger mathematisch denkenden Menschen seine Bedeutung klarer:

mid = start + (end - start) / 2

liest als:

Mitte gleich Start plus die Hälfte der Länge.

wohingegen:

mid = (start + end) / 2

liest als:

Mitte entspricht der Hälfte von Start plus Ende

Was nicht so klar zu sein scheint wie das erste, zumindest wenn man es so ausdrückt.

wie Kos betonte, kann es auch lesen:

mid entspricht dem Durchschnitt von Start und Ende

Was klarer ist, aber meiner Meinung nach immer noch nicht so klar wie das erste.

start + (end-start) / 2 kann einen möglichen Überlauf vermeiden, zum Beispiel start = 2 ^ 20 und end = 2 ^ 30