Pallavi Chauhan
Ich habe gesehen, wie Programmierer die Formel verwenden
mid = start + (end - start) / 2
anstatt die einfachere Formel zu verwenden
mid = (start + end) / 2
um das mittlere Element im Array oder in der Liste zu finden.
Warum verwenden sie das erstere?
Dietrich Ep
Es gibt drei Gründe.
Zuerst, start + (end - start) / 2 funktioniert auch, wenn Sie Zeiger verwenden, solange end - start läuft nicht über1.
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) / 2 wird nicht überlaufen, wenn start und end sind große positive Zahlen. Bei vorzeichenbehafteten 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 end - start kann überlaufen, aber nur wenn start < 0 oder end < 0.)
Oder bei vorzeichenloser Arithmetik ist ein Überlauf definiert, gibt Ihnen aber die falsche Antwort. Für vorzeichenlose Operanden gilt jedoch: start + (end - start) / 2 wird nie ü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öchte man oft in Richtung runden start Element.
int start = -3, end = 0;
int mid = start + (end - start) / 2; // -2, closer to start
int mid = (start + end) / 2; // -1, surprise!
1 Wenn das Ergebnis der Pointer-Subtraktion gemäß dem C-Standard nicht als a darstellbar ist ptrdiff_t, dann ist das Verhalten undefiniert. In der Praxis erfordert dies jedoch die Zuweisung von a char Array, das mindestens die Hälfte des gesamten Adressraums verwendet.
Ergebnis von (end - start) in dem signed int case ist undefiniert, wenn er überläuft.
– einschl
31. Juli 2016 um 20:52 Uhr
Kannst du das beweisen end-start wird nicht überlaufen? AFAIK, wenn Sie ein Negativ nehmen start es sollte möglich sein, es zum Überlaufen zu bringen. Sicher, meistens, wenn Sie den Durchschnitt berechnen, wissen Sie, dass die Werte sind >= 0 …
– Bakuriu
31. Juli 2016 um 21:28 Uhr
@Bakuriu: Es ist unmöglich, etwas zu beweisen, das nicht wahr ist.
– Dietrich Ep
31. Juli 2016 um 23:07 Uhr
Es ist von besonderem Interesse in C, da die Zeigersubtraktion (gemäß dem Standard) vom Design her gebrochen ist. Implementierungen dürfen so große Arrays erstellen end - start ist undefiniert, da Objektgrößen ohne Vorzeichen sind, während Zeigerunterschiede vorzeichenbehaftet sind. So end - start “funktioniert sogar mit Zeigern”, vorausgesetzt, Sie halten auch irgendwie die Größe des darunter liegenden Arrays ein PTRDIFF_MAX. Um dem Standard gerecht zu werden, ist dies auf den meisten Architekturen kein großes Hindernis, da dies die Hälfte der Größe der Speicherzuordnung ist.
– Steve Jessop
1. August 2016 um 11:03 Uhr
@Bakuriu: Übrigens gibt es im Beitrag eine Schaltfläche “Bearbeiten”, mit der Sie Änderungen vorschlagen (oder selbst vornehmen) können, wenn Sie der Meinung sind, dass ich etwas verpasst habe oder etwas unklar ist. Ich bin nur ein Mensch, und dieser Beitrag wurde von über zweitausend Augäpfeln gesehen. Die Art von Kommentar, “Du solltest das klären …”, reibt mich wirklich in die falsche Richtung.
– Dietrich Ep
1. August 2016 um 14:02 Uhr
Schubham
Wir können ein einfaches Beispiel nehmen, um diese Tatsache zu demonstrieren. Angenommen, in einem bestimmten groß array, versuchen wir den Mittelpunkt des Bereichs zu finden [1000, INT_MAX]. Jetzt, INT_MAX ist der größte Wert der int Datentyp speichern kann. Selbst wenn 1 dazu addiert, wird der Endwert negativ.
Ebenfalls, start = 1000 und end = INT_MAX.
Mit der Formel: (start + end)/2,
der Mittelpunkt wird sein
(1000 + INT_MAX)/2=-(INT_MAX+999)/2welches ist Negativ und kann einen Segmentierungsfehler verursachen wenn wir versuchen, mit diesem Wert zu indizieren.
Aber mit der Formel (start + (end-start)/2)wir bekommen:
(1000 + (INT_MAX-1000)/2)=(1000 + INT_MAX/2 - 500)=(INT_MAX/2 + 500)die nicht überlaufen.
Wenn Sie 1 zu addieren INT_MAXist das Ergebnis nicht negativ, sondern undefiniert.
– Celtschk
1. August 2016 um 21:46 Uhr
@celtschk Theoretisch ja. Praktisch wird es viele Male herumlaufen INT_MAX zu -INT_MAX. Es ist jedoch eine schlechte Angewohnheit, sich darauf zu verlassen.
– Mast
2. August 2016 um 9:46 Uhr
DerLethalCoder
Um das zu ergänzen, was andere bereits gesagt haben, erklärt der erste seine Bedeutung klarer für diejenigen, die weniger mathematisch interessiert sind:
mid = start + (end - start) / 2
liest sich wie folgt:
Mitte gleich Anfang plus halbe Länge.
wohingegen:
mid = (start + end) / 2
liest sich wie folgt:
Mitte ist die Hälfte von Anfang plus Ende
Was nicht so klar erscheint wie das erste, zumindest wenn man es so ausdrückt.
wie Kos betonte, kann es auch lauten:
Mitte entspricht dem Durchschnitt von Anfang und Ende
Das ist klarer, aber meiner Meinung nach immer noch nicht so klar wie das erste.
Ich verstehe Ihren Punkt, aber das ist wirklich eine Strecke. Wenn Sie „e – s“ sehen und an „Länge“ denken, dann sehen Sie fast sicher „(s+e)/2“ und denken an „durchschnittlich“ oder „mittel“.
– Djechlin
1. August 2016 um 22:57 Uhr
@djechlin Programmierer sind schlecht in Mathe. Sie sind mit ihrer Arbeit beschäftigt. Sie haben keine Zeit, den Mathematikunterricht zu besuchen.
– Kleiner Außerirdischer
2. August 2016 um 5:01 Uhr
start + (end-start) / 2 kann einen möglichen Überlauf vermeiden, zum Beispiel start = 2^20 und end = 2^30
Wilde Vermutung:
(start + end)könnte überlaufen, während(end - start)kann nicht.– Cadaniluk
31. Juli 2016 um 20:15 Uhr
weil letzteres nicht funktioniert wenn
startundendsind Zeiger.– einschl
31. Juli 2016 um 20:20 Uhr
Extra, Extra – Lesen Sie alles darüber: Fast jede binäre Suche und jedes Mergesort ist kaputt
– Jonathan Leffler
31. Juli 2016 um 21:08 Uhr
start + (end - start) / 2hat auch semantische Bedeutung:(end - start)ist die Länge, also heißt es:start + half the length.– njzk2
1. August 2016 um 2:16 Uhr
@LưuVĩnhPhúc: Hat diese Frage nicht die besten Antworten und die meisten Stimmen? Wenn ja, sollten die anderen Fragen wahrscheinlich als Duplikat dieser Frage geschlossen werden. Das Alter der Beiträge spielt keine Rolle.
– Nisse Engström
2. August 2016 um 12:08 Uhr