wyjaśnić różnicę między tych algorytmów MIDPOINT

Question

Dlaczego midpoint algorytm Binary Search korzystania

low + (high-low)/2 

zamiast

(low + high)/2 

Answer 1

Twoje pytanie zostało oznaczone jako python, więc odpowiem na pytanie Pythona. W skrócie, to nie:

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

pythonic realizacja powyżej found in the docs wykorzystuje ostatnią konstrukcję. Jak zauważyli ludzie w komentarzach, some languages need to respect overflow. Python isn't none of them i ma arbitralne liczby całkowite.

W komentarzach spekulowano, że ktoś przenoszący z języka podobnego do C może skopiować bardziej akceptowalną konstrukcję dla tego języka. To jest możliwe. Ktoś inny zauważył, że jeden może być szybszy od drugiego; taka mikro-optymalizacja wydaje się być trudna do komentowania w ogóle.

Ale ... co, jeśli nie są Ints!

Założono, że są to liczby całkowite, ponieważ w przypadku wyszukiwania binarnego indeksy są liczbami całkowitymi. Jeśli w rzeczywistości nie są liczbami całkowitymi, będziesz miał problemy z ich użyciem do uzyskania tablic.Ale w tym czasie, można experiene różne wyniki:

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

Podobnie

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

Ten ostatni przykład jest inna, choć nie jest to dla mnie jasne, co jest lepsze. Dlaczego tak się dzieje, możesz spojrzeć na wyjaśnienia dotyczące przelewu w artykule, do którego link znajduje się powyżej.

Answer 2

Szukałem na to pytanie na google i znalazłem bardzo ciekawą odpowiedź na http://googleresearch.blogspot.in/2006/06/extra-extra-read-all-about-it-nearly.html

Oto przykład:

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:  } 

Błąd jest w tym wierszu:

int mid =(low + high)/2; 

w programowaniu Perły Bentley mówi, że analogiczna linia „ustawia m do średniej L i U, obcięty dół do najbliższej liczby całkowitej.” Na pierwszy rzut oka, to stwierdzenie może wydawać się poprawne, ale zawodzi w przypadku dużych wartości zmiennych int niskich i wysokich. W szczególności zawiedzie, jeśli suma wartości niskiej i wysokiej jest większa niż maksymalna dodatnia wartość int (231-1). Suma przepełnia się do wartości ujemnej, a wartość pozostaje ujemna po podzieleniu przez dwa. W C powoduje to indeks tablicy poza zasięgiem nieprzewidywalnych wyników. W Javie generuje wyjątek ArrayIndexOutOfBoundsException.

Ten błąd może objawiać się dla tablic, których długość (w elementach) wynosi 230 lub więcej (około miliarda elementów). Było to nie do pomyślenia w latach 80., kiedy pisano Perełki programistyczne, ale obecnie jest powszechne w Google i innych miejscach. W programowaniu pereł Bentley mówi: "Podczas gdy pierwsze wyszukiwanie binarne zostało opublikowane w 1946 roku, pierwsze wyszukiwanie binarne, które działa poprawnie dla wszystkich wartości n, pojawiło się dopiero w 1962 roku." Prawda jest taka, że ​​opublikowano bardzo mało poprawnych wersji, przynajmniej w głównych językach programowania.

Jaki jest najlepszy sposób na naprawienie błędu? Oto jeden sposób:

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