Wpisany przez Tomasz Lubiński,
04 września 2009 20:00
Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej zadany element x. Niech będzie to tablica a o indeksach od 1 do n. Czyli kolejne jej elementy oznaczymy: a[1], a[2], a[3], ..., a[n-1], a[n].
Jeżeli elementy w tej tablicy są posortowane, to możemy użyć bardzo szybkiego algorytmu wyszukiwania połówkowego, zwanego też wyszukiwaniem binarnym. Poniżej przedstawię jego wersję dla tablicy posortowanej rosnąco. Nazwa tego algorytmu pochodzi od sposobu w jaki szukany jest element. Załóżmy, że początkowy indeks naszej tablicy oznaczony jest indeksem l a końcowy indeks tablicy oznaczony jest p. Na początku oczywiście l = 1 a p = n. Dzielimy tą tablicę na pół elementem o indeksie równym s = (l + p) / 2, przy czym dzielenie to jest dzieleniem bez reszty, tak by uzyskać liczbę całkowitą (w końcu indeksy elementów w naszej tablicy są liczbami całkowitymi). Sprawdzamy czy element o indeksie s jest szukanym elementem, jeżeli tak to kończymy działanie algorytmu gdyż odnaleźliśmy szukany element. W przeciwnym razie sprawdzamy czy element pod indeksem s jest większy od szukanego. Jeżeli tak jest to wiemy, że elementy o indeksach s+1, s+2, ...p również są większe (wynika, to z faktu, że tablica jest posortowana rosnąco). Zatem wiemy już że tamtej części nie ma co szukać, ustawiamy zatem indeks końca tablicy p na wartość s-1 i powtarzamy dzielenie tej tablicy na pół tak, jak już to było opisane wcześniej. Gdy element pod indeksem s jest mniejszy od szukanego to wiemy, że również elementy o indeksach s-1, s-2, ...l są mniejsze od elementu szukanego (wynika, to z faktu, że tablica jest posortowana rosnąco). Zatem wiemy już że tamtej części nie ma co szukać, ustawiamy zatem indeks początku tablicy l na wartość s+1 i powtarzamy dzielenie tej tablicy na pół tak, jak już to było opisane wcześniej. Opisane czynności wykonujemy tak długo aż znajdziemy szukany element bądź wskaźnik początku tablicy l będzie większy od wskaźnika końca tablicy p. Jeżeli tak się stanie oznacza to, że szukanego elementu nie ma w przeszukiwanej tablicy.
Operację szukania połówkowego (binarnego) możemy zapisać następującym schematem blokowym:
Algorytm ten ma bardzo dobrą złożoność obliczeniową wynoszącą O(log n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób logarytmiczny wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy.
Niech będzie dana tablica 5-elementowa, a = {1, 2, 4, 6, 7}.
Poszukajmy w niej element x = 2.
Na początku l = 1, p = 5.
Wybieramy element środkowy s = (1 + 5) / 2 = 3.
Sprawdzamy czy a[3] jest równe 2? Nie, element ten jest równy 4, jest on większy od 2 zatem modyfikujemy p = s - 1 = 3 - 1 = 2.
Wybieramy element środkowy s = (1 + 2) / 2 = 1.
Sprawdzamy czy a[1] jest równe 2? Nie, element ten jest równy 1, jest on mniejszy od 2 zatem modyfikujemy l = s + 1 = 1 + 1 = 2.
Wybieramy element środkowy s = (2 + 2) / 2 = 2.
Sprawdzamy czy a[2] jest równe 2? Tak, znaleźliśmy szukany element pod indeksem 2.
Poszukajmy teraz element x = 5.
Na początku l = 1, p = 5.
Wybieramy element środkowy s = (1 + 5) / 2 = 3.
Sprawdzamy czy a[3] jest równe 5? Nie, element ten jest równy 4, jest on mniejszy od 5 zatem modyfikujemy l = s + 1 = 3 + 1 = 4.
Wybieramy element środkowy s = (4 + 5) / 2 = 4.
Sprawdzamy czy a[4] jest równe 5? Nie, element ten jest równy 6, jest on większy od 5 zatem modyfikujemy p = s - 1 = 3.
W tym momencie l jest większe od p, zatem kończymy wyszukiwanie. Elementu o wartości 5 nie ma w przeszukiwanej tablicy.
Przykład w JavaScript
Jeżeli elementy w tej tablicy są posortowane, to możemy użyć bardzo szybkiego algorytmu wyszukiwania połówkowego, zwanego też wyszukiwaniem binarnym. Poniżej przedstawię jego wersję dla tablicy posortowanej rosnąco. Nazwa tego algorytmu pochodzi od sposobu w jaki szukany jest element. Załóżmy, że początkowy indeks naszej tablicy oznaczony jest indeksem l a końcowy indeks tablicy oznaczony jest p. Na początku oczywiście l = 1 a p = n. Dzielimy tą tablicę na pół elementem o indeksie równym s = (l + p) / 2, przy czym dzielenie to jest dzieleniem bez reszty, tak by uzyskać liczbę całkowitą (w końcu indeksy elementów w naszej tablicy są liczbami całkowitymi). Sprawdzamy czy element o indeksie s jest szukanym elementem, jeżeli tak to kończymy działanie algorytmu gdyż odnaleźliśmy szukany element. W przeciwnym razie sprawdzamy czy element pod indeksem s jest większy od szukanego. Jeżeli tak jest to wiemy, że elementy o indeksach s+1, s+2, ...p również są większe (wynika, to z faktu, że tablica jest posortowana rosnąco). Zatem wiemy już że tamtej części nie ma co szukać, ustawiamy zatem indeks końca tablicy p na wartość s-1 i powtarzamy dzielenie tej tablicy na pół tak, jak już to było opisane wcześniej. Gdy element pod indeksem s jest mniejszy od szukanego to wiemy, że również elementy o indeksach s-1, s-2, ...l są mniejsze od elementu szukanego (wynika, to z faktu, że tablica jest posortowana rosnąco). Zatem wiemy już że tamtej części nie ma co szukać, ustawiamy zatem indeks początku tablicy l na wartość s+1 i powtarzamy dzielenie tej tablicy na pół tak, jak już to było opisane wcześniej. Opisane czynności wykonujemy tak długo aż znajdziemy szukany element bądź wskaźnik początku tablicy l będzie większy od wskaźnika końca tablicy p. Jeżeli tak się stanie oznacza to, że szukanego elementu nie ma w przeszukiwanej tablicy.
Operację szukania połówkowego (binarnego) możemy zapisać następującym schematem blokowym:
Algorytm ten ma bardzo dobrą złożoność obliczeniową wynoszącą O(log n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób logarytmiczny wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy.
Przykład:
Niech będzie dana tablica 5-elementowa, a = {1, 2, 4, 6, 7}.
Poszukajmy w niej element x = 2.
Na początku l = 1, p = 5.
Wybieramy element środkowy s = (1 + 5) / 2 = 3.
Sprawdzamy czy a[3] jest równe 2? Nie, element ten jest równy 4, jest on większy od 2 zatem modyfikujemy p = s - 1 = 3 - 1 = 2.
Wybieramy element środkowy s = (1 + 2) / 2 = 1.
Sprawdzamy czy a[1] jest równe 2? Nie, element ten jest równy 1, jest on mniejszy od 2 zatem modyfikujemy l = s + 1 = 1 + 1 = 2.
Wybieramy element środkowy s = (2 + 2) / 2 = 2.
Sprawdzamy czy a[2] jest równe 2? Tak, znaleźliśmy szukany element pod indeksem 2.
Poszukajmy teraz element x = 5.
Na początku l = 1, p = 5.
Wybieramy element środkowy s = (1 + 5) / 2 = 3.
Sprawdzamy czy a[3] jest równe 5? Nie, element ten jest równy 4, jest on mniejszy od 5 zatem modyfikujemy l = s + 1 = 3 + 1 = 4.
Wybieramy element środkowy s = (4 + 5) / 2 = 4.
Sprawdzamy czy a[4] jest równe 5? Nie, element ten jest równy 6, jest on większy od 5 zatem modyfikujemy p = s - 1 = 3.
W tym momencie l jest większe od p, zatem kończymy wyszukiwanie. Elementu o wartości 5 nie ma w przeszukiwanej tablicy.
Przykład w JavaScript
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C# | MS Visual Studio .net | .cs | .cs | ***** / 4 |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 12 | |
Marian | C/C++ | C++ | .cpp | .cpp | ***** / 21 |
Kamil Dębowski | C/C++ | wersja używająca rekursji | .cpp | .cpp | ***** / 3 |
Krzysztof Sośnierz | C/C++ | C++ templates | .cpp | .cpp | ***** / 7 |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 6 | |
Tomasz Lubiński | Java | .java | .java | ***** / 4 | |
Dominik Goździuk | JavaScript | .js | .js | ***** / 2 | |
Dominik Goździuk | Perl | .pl | .pl | ***** / 1 | |
Karol Nowacki | Php | .php | .php | ***** / 2 | |
Maskara | Python | .py | .py | ***** / 11 |
Poprawiony: 12 marca 2012 20:31
Na początku a= 1 , f= 6
Wybieramy element środkowy s = (1 + 6) / 2 =3,5 więc trzeba by było zaokrąglić w góre lub w dół
Może lepiej było by oznaczyć to działanie jako s=(l + p) div 2, ale przecież autor zaznaczył że chodzi o dzielenie bez reszty. Czytajcie ze zrozumieniem!
Cytat: