Spiegare la differenza tra questi Punto medio Algoritmi

Question

Perché l'algoritmo punto centrale per la ricerca binaria utilizzare

low + (high-low)/2 

piuttosto che

(low + high)/2 

Answer 1

La tua domanda è codificata per python, quindi risponderò per python. In breve, non è così:

https://hg.python.org/cpython/file/2.7/Lib/bisect.py

L'attuazione pythonic sopra found in the docs utilizza quest'ultimo costruzione. Come hanno sottolineato le persone nei commenti, some languages need to respect overflow. Python isn't none of them e ha numeri interi di precisione arbitrari.

Nei commenti è stato ipotizzato che qualcuno porting da un linguaggio simile a C potrebbe copiare la costruzione più accettabile per quella lingua. Questo è possibile. Qualcun altro ha commentato che uno potrebbe essere più veloce dell'altro; una tale micro-ottimizzazione sembra essere difficile da commentare in generale.

Ma ... cosa succede se non sono Ints!

Ho assunto che questi sono numeri interi perché per la ricerca binaria gli indici sono numeri interi. Se in effetti non sono numeri interi, si avranno problemi nell'utilizzarli per accedere agli array.Ma nel frattempo, si potrebbe offrono dell'ottimo risultati diversi:

a = b = sys.float_info.max 
print a + (a-b)/2 # prints a really big number 
print (a+b)/2 # prints inf 

Allo stesso modo,

a = b = float("inf") 
print a+(a-b)/2 # prints nan 
print (a+b)/2 # prints inf 

Quest'ultimo esempio è diversa, anche se non è chiaro per me che è meglio. Per il motivo per cui ciò si verifica, è possibile consultare le spiegazioni di overflow nell'articolo collegato sopra.

Answer 2

Ho cercato questa domanda su google e ho trovato risposta molto interessante sul http://googleresearch.blogspot.in/2006/06/extra-extra-read-all-about-it-nearly.html

Ecco un esempio:

1:  public static int binarySearch(int[] a, int key) { 
2:   int low = 0; 
3:   int high = a.length - 1; 
4: 
5:   while (low <= high) { 
6:    int mid = (low + high)/2; 
7:    int midVal = a[mid]; 
8: 
9:    if (midVal < key) 
10:     low = mid + 1 
11:    else if (midVal > key) 
12:     high = mid - 1; 
13:    else 
14:     return mid; // key found 
15:   } 
16:   return -(low + 1); // key not found. 
17:  } 

L'errore è in questa linea:

int mid =(low + high)/2; 

In Programming Pearls Bentley dice che la riga analogo "imposta m alla media di L ed U, troncato al numero intero più vicino." A prima vista, questa affermazione potrebbe sembrare corretta, ma fallisce per grandi valori delle variabili int basse e alte. In particolare, fallisce se la somma di basso e alto è maggiore del valore massimo positivo int (231 - 1). La somma passa a un valore negativo e il valore rimane negativo se diviso per due. In C ciò causa un indice di array fuori limite con risultati imprevedibili. In Java, lancia ArrayIndexOutOfBoundsException.

Questo errore può manifestarsi per gli array la cui lunghezza (in elementi) è maggiore o uguale a 230 (circa un miliardo di elementi). Questo era inconcepibile negli anni '80, quando fu scritto Programming Pearls, ma è comune in questi giorni a Google e in altri luoghi. In Programmazione perle, Bentley dice "Mentre la prima ricerca binaria è stata pubblicata nel 1946, la prima ricerca binaria che funziona correttamente per tutti i valori di n non è apparsa prima del 1962." La verità è che sono state pubblicate pochissime versioni corrette, almeno nei linguaggi di programmazione tradizionali.

Quindi qual è il modo migliore per correggere l'errore? Ecco un modo:

int mid = low + ((high - low)/2);