algorytm.org

Szukanie połówkowe (binarne)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szukanie połówkowe (binarne)
Ocena użytkowników:***** / 49
SłabyŚwietny 
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:

schemat blokowy - wyszukanie połówkowe (binarne)


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

Podaj szukaną liczbę:



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 4
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 9
MarianC/C++C++
.cpp
.cpp
***** / 13
Kamil DębowskiC/C++wersja używająca rekursji
.cpp
.cpp
***** / 3
Krzysztof SośnierzC/C++C++ templates
.cpp
.cpp
***** / 5
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 6
Tomasz LubińskiJava
.java
.java
***** / 4
Dominik GoździukJavaScript
.js
.js
***** / 1
Dominik GoździukPerl
.pl
.pl
***** / 1
Karol NowackiPhp
.php
.php
***** / 2
MaskaraPython
.py
.py
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 12 marca 2012 20:31
Komentarze
photo
-1 # burza 2013-08-13 14:24
a co by było gdyby tablica była 6-elementowa to wtedy by było tak :
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ół
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # Witamaster 2013-09-28 19:53
W tym algorytmie wykonywane jest dzielenie bez reszty, czyli zaokrąglone w dół. W tym przypadku s= (1+6)/2 = 3,5. Bez reszty s=3.
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:
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ą (...)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz