per trovare l'elemento centrale in un vettore, perché utilizzare "mid = beg + (end - beg)/2" anziché "mid = (beg + end)/2"

Question

Sono nuovo al C++. Ho visto questo codice online, dove sta cercando di trovare una stringa all'interno di un vettore. Tuttavia, ho notato a destra verso la fine:

mid = beg + (end - beg)/2; 

Perché deve essere scritto in questo modo, perché non può essere scritto come:

mid = (beg + end) /2 

È mid = (beg + (end - 1))/2 un'alternativa fattibile?

Sto lottando per capire il motivo dietro di esso.

Answer 1

In generale con la ricerca binaria, il motivo è evitare l'overflow. beg+end è soggetto a overflow con valori elevati. L'utilizzo di end-beg evita l'overflow.

Immaginate di beg era MAX_INT-3 e end era MAX_INT-1, quindi beg+end sarebbe più grande di MAX_INT, ma end-beg, sarebbe solo 2.

Con iteratori, questo funziona anche fuori perché end-begin è un numero, mentre begin+end è non valido. Puoi sottrarre due iteratori per ottenere la distanza tra di loro, ma non puoi aggiungere due iteratori.

Answer 2

L'aggiunta di due iteratori non ha senso e non è possibile farlo.

È possibile chiamare operator- su due iteratori e fornire un risultato ragionevole, ovvero il conteggio degli elementi tra due iteratori. E puoi aggiungere o sottrarre un numero intero su iteratore, significa spostarlo avanti o indietro. Ma quale dovrebbe essere il risultato dell'aggiunta di due iteratori?

mid = beg + (end - beg)/2; 
      ~~~~~~~~~~  => get the count between beg and end 
      ~~~~~~~~~~~~~~~ => get the half of the count 
     ~~~~~~~~~~~~~~~~~~~~~ => get the iterator pointing to the middle position between beg and end 

mid = (beg + end) /2 
     ~~~~~~~~~ => What would the result represent?