Wykop.pl

Wykopalisko (245) Hity Mikroblog

Czytaliście "Perełki programowania"? Autor pisze tam że pierwsze wyszukiwanie binarne zostało opisane w 1946 ale dopiero w 1962 udało się stworzyć bezbłędną wersję tego algorytmu. Okazało się, że nawet wersja opisana w Perełkach (i z dowodem poprawności) zawiera błąd...

Dodany z googleresearch.blogspot.com do Technologia » Nowe technologie z tagami algorytm binarne błąd java programowanie przepełnienie wyszukiwanie

Wykopali 23, zakopali 0

NOWY Windows 7 Home Premium OEM PL 32 Bit FVat23% Cena: 365.00 zł
Telefon Nokia 500 Cena: 499.00 zł
Samochód do przewozu osoby niepełnosprawnej Cena: 11500.00 zł

Allegro.pl

Wymagana obsługa JavaScript

Żeby w pełni skorzystać z nowych funkcji włącz obsługę JavaScript lub zmień przeglądarkę na taką, która go wspiera.

niezaminusowane

Pokaż: ustaw jako domyślne

pokaż obrazki

Komentarze (9)

Reklamy Google
kkll 5 lat 8 mies. temu +1

Implementacja na 31-bitowych intach obsługuje poprawnie "tylko" 2^30 elementów! AAAaaa, jakie straszne! ;)
- #
pokaż komentarz
Polinik 5 lat 8 mies. temu +1

Przy dodawaniu nowych linkow mozna (wrecz trzeba) zdefiniowac w jakim jezyku jest tresc pod linkiem.
Nie dodawaj obcojezycznych linkow jako polskojezyczne, dobrze?
- #
pokaż komentarz
ponton 5 lat 8 mies. temu 0

Zamiast tego można zrobić tak:

int mid = low + (high-low) / 2;
- #
pokaż komentarz
SasQ 1 rok 4 mies. temu 0

@ponton: Dla mnie to by było oczywiste i samonasuwające się rozwiązanie. Tamto to jakaś droga na około...
- #
pokaż komentarz
pawlak 5 lat 8 mies. temu 0

LOL, na tej samej zasadzie błędny jest każdy algorytm, który można błędnie zaimplementować, doprowadzając do przepełnienia liczby całkowitej. Problem leży nie w algorytmie, tylko w nieuważnym implementowaniu go. Spostrzeżenie niewątpliwie ciekawe, lecz wyszukiwanie binarne i merge sort jako takie są jak najbardziej poprawne.
- #
pokaż komentarz
piotrb 5 lat 8 mies. temu -1

Przecież wystarczy dodać kolejne 32 bity i będzie dobrze, w końcu liczba danych i tak przekroczy 2^32 i wtedy long long będzie ok. Naprawdę nie pojmuje w czym problem.
- #
pokaż komentarz
SasQ 1 rok 4 mies. temu -1

@piotrb: W tym, że dodając bity liczby zwiększa się zazwyczaj jednocześnie przestrzeń adresowa, więc ten algorytm będzie się przepełniać niezależnie od tego, ile bitów użyjesz.
- #
pokaż komentarz
pawlak 5 lat 8 mies. temu -1

kkll: ale błąd jest.
- #
pokaż komentarz
pawlak 5 lat 8 mies. temu -1

Jest tam takie rozwiązanie, tylko z dodatkowymi nawiasami.
- #
pokaż komentarz