Mengapa memilih awal + (akhir - awal) / 2 daripada (mulai + akhir) / 2 saat menghitung tengah array?

Saya telah melihat programmer menggunakan formula

mid = start + (end - start) / 2

alih-alih menggunakan rumus yang lebih sederhana

mid = (start + end) / 2

untuk menemukan elemen tengah dalam array atau daftar.

Mengapa mereka menggunakan yang sebelumnya?

Ada tiga alasan.

Pertama-tama, start + (end - start) / 2berfungsi bahkan jika Anda menggunakan pointer, asalkan end - starttidak melimpah ¹ .

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

Kedua, start + (end - start) / 2tidak akan meluap jika startdan endmerupakan angka positif yang besar. Dengan operan yang ditandatangani, overflow tidak ditentukan:

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

(Perhatikan bahwa end - startmungkin meluap, tetapi hanya jika start < 0atau end < 0.)

Atau dengan aritmatika yang tidak ditandatangani, overflow didefinisikan tetapi memberi Anda jawaban yang salah. Namun, untuk operan yang tidak ditandatangani, start + (end - start) / 2tidak akan pernah meluap selama end >= start.

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

Akhirnya, Anda sering ingin membulatkan ke startelemen.

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

Catatan kaki

¹ Menurut standar C, jika hasil pengurangan pointer tidak dinyatakan sebagai a ptrdiff_t, maka perilaku tidak terdefinisi. Namun, dalam praktiknya, ini membutuhkan mengalokasikan chararray menggunakan setidaknya setengah dari seluruh ruang alamat.

Kita dapat mengambil contoh sederhana untuk menunjukkan fakta ini. Misalkan dalam array besar tertentu , kami mencoba menemukan titik tengah rentang [1000, INT_MAX]. Sekarang, INT_MAXadalah nilai terbesar yang intbisa disimpan oleh tipe data. Bahkan jika 1ditambahkan ke ini, nilai akhir akan menjadi negatif.

Juga, start = 1000dan end = INT_MAX.

Menggunakan rumus: (start + end)/2,

titik tengah akan menjadi

(1000 + INT_MAX)/2= -(INT_MAX+999)/2, yang negatif dan dapat memberikan kesalahan segmentasi jika kami mencoba mengindeks menggunakan nilai ini.

Tapi, menggunakan rumus (start + (end-start)/2),, kita mendapatkan:

(1000 + (INT_MAX-1000)/2)= (1000 + INT_MAX/2 - 500)= (INT_MAX/2 + 500) yang tidak akan meluap .

Untuk menambah apa yang sudah dikatakan orang lain, yang pertama menjelaskan artinya lebih jelas bagi mereka yang kurang berpikir matematis:

mid = start + (end - start) / 2

terbaca sebagai:

pertengahan sama dengan awal ditambah setengah dari panjang.

sedangkan:

mid = (start + end) / 2

terbaca sebagai:

mid sama dengan setengah dari awal plus akhir

Yang sepertinya tidak sejelas yang pertama, setidaknya ketika diungkapkan seperti itu.

seperti yang ditunjukkan Kos itu juga dapat membaca:

mid sama dengan rata-rata awal dan akhir

Yang lebih jelas tapi tetap tidak, setidaknya menurut saya, sejelas yang pertama.

start + (end-start) / 2 dapat menghindari kemungkinan overflow, misalnya start = 2 ^ 20 dan end = 2 ^ 30