algorytm.org

Szukanie elementu z wartownikiem

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 elementu z wartownikiem
Ocena użytkowników:***** / 33
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 04 września 2009 19:47

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 przyjrzymy się dokładnie klasycznemu algorytmowi przeglądania tablicy w poszukiwaniu elementu:

schemat blokowy - szukanie elementu w tablicy


zauważymy, że dla każdego elementu wykonywane są dwa porównania:

Liczbę porównań można zredukować wykorzystując algorytm wyszukiwania z wartownikiem. Nazwa tego algorytmu bierze się ze sposobu, w jaki wykorzystywany jest element szukany x.

By odnaleźć element x podejmiemy następujące kroki:


W stosunku do klasycznego algorytmu wyszukiwania oszczędzamy czas na sprawdzaniu czy osiągnęliśmy koniec tablicy. Sprawdzenie to występuje raz - po odnalezieniu elementu szukanego, a nie tak jak poprzednio przed każdym sprawdzeniem kolejnego elementu.
Operację odnajdowania elementu w tablicy z wartownikiem możemy zapisać następującym schematem blokowym:

schemat blokowy - szukanie elementu w tablicy z wartownikiem


Algorytm ten mimo, że jest szybszy od zwykłego wyszukiwania to ma taką samą jak on złożoność obliczeniową wynoszącą O(n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób liniowy wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. To znaczy, że czas potrzebny na wyszukanie dwa razy większej liczby elementów wzrośnie dwukrotnie.
Podczas implementowania tego rozwiązania należy zapewnić miejsce w tablicy potrzebne do dodania wartownika. Należy więc deklarować tablicę o rozmiarze o jeden większym jak liczba przechowywanych elementów.

Przykład:

Niech będzie dana tablica 5-elementowa, a = {4, 6, 2, 1, 3}.
Poszukajmy w niej element x = 2.
Dodajemy na końcu tablicy element o wartości 2, czyli a[6] = 2.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 2, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 2, przechodzimy do kolejnego elementu,
a[3] = x? 2 jest równe 2, element znaleźliśmy pod indeksem 3, nie jest to ostatni element tablicy zatem znaleźliśmy szukany element.

Poszukajmy teraz element x = 5.
Dodajemy na końcu tablicy element o wartości 5, czyli a[6] = 5.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 5, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 5, przechodzimy do kolejnego elementu,
a[3] = x? 2 nie jest równe 5, przechodzimy do kolejnego elementu,
a[4] = x? 1 nie jest równe 5, przechodzimy do kolejnego elementu,
a[5] = x? 3 nie jest równe 5, przechodzimy do kolejnego elementu,
a[6] = x? 5 jest równe 5, element znaleźliśmy pod indeksem 6, jest to ostatni element tablicy zatem nie znaleźliśmy szukanego elementu a jedynie natrafiliśmy na naszego wartownika, który zabezpieczył nas przed wyjściem poza zakres tablicy. Werdykt zatem brzmi: elementu 5 nie ma w przeszukiwanej tablicy.

Przykład w JavaScript:
Tablica liczb (wartości oddzielone przecinkiem, bez spacji):
Szukana wartosc:

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 0
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 5
MarianC/C++C++
.cpp
.cpp
***** / 3
Krzysztof SośnierzC/C++C++ templates
.cpp
.cpp
***** / 0
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 0
Tomasz LubińskiJava
.java
.java
***** / 3
Tomasz LubińskiJavaScript
.js
.js
***** / 0
Tomasz LubińskiJavaScriptz automatycznym opisem kroków algorytmu
.js
.js
***** / 0
Dominik GoździukPhp
.php
.php
***** / 2
 
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: 07 lutego 2013 08:41
Komentarze
photo
0 # KaRi 2010-06-02 19:53
lajt czekamy na więcej
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-3 # Gość 2010-09-11 23:51
Hmm...a co z przypadkiem kiedy w tablicy są np. dwa poszukiwane elementy?. Gdy znajdzie pierwszy to stwierdzi że nie jest to ostatni element i wypisze że znaleziono element itd ale zakończy działanie...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Wasyl 2011-03-14 16:10
Cytuję Gość:
Hmm...a co z przypadkiem kiedy w tablicy są np. dwa poszukiwane elementy?. Gdy znajdzie pierwszy to stwierdzi że nie jest to ostatni element i wypisze że znaleziono element itd ale zakończy działanie...

Myślę że jeśli musisz znaleźć wszystkie to wtedy po znalezieniu elementu dodajesz do jakiejś tablicy w którym miejscu znajduje się szukany element, potem przechodzisz do warunku i=n+1 i jeśli i nie jest równe n+1 to wracasz do i = i+1. Nadal algorytm jest szybszy, bo warunek i=n+1 sprawdzasz tylko przy każdym wystąpieniu szukanej wartości a nie za każdym razem.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-3 # zc 2012-06-12 09:58
nie bardzo rozumiem. jeśli tablica jest 5-elementowa to nie można sobie zrobić np. a[6]=2 bo wtedy wywala błąd...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Witamaster 2012-06-16 10:43
Musisz dopisać do tablicy szósty element - wartownik.

C++
"tablica = new double[ilosc+1];"
Ustalasz długość tablicy o 1 większą niż ilość danych.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Tomasz Lubiński 2013-02-07 08:44
W C++ czy Javie 5-elementowa tablica ma następujące odwołania: a[0], a[1], a[2], a[3], a[4], zatem szósty element będzie pod indeksem numer 5 (bo indeksy w tych językach zaczynają się od 0), czyli wartownika wpisujemy pod a[5].
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Anonymous 2013-01-24 22:58
Czy w tym przypadku nie ma możliwości wyjścia poza tablicę?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Witamaster 2013-01-31 19:55
Wartownik stosuje się właśnie po to by algorytm nie mógł "wyjść" po za tablicę. Do końca tablicy dopisuje się element - wartownik. Jeśli algorytm dotrze do wartownika, oznacza to że przeszukał całą tablicę i powinien zakończyć działanie.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # grom 2015-05-22 08:45
jak dla mnie jest tu mały błąd, bo algorytm szuka danej liczby ale jeśli jej nie znajdzie ORAZ (co widać przykładzie drugim w którym szukany element jest wartownikiem) szukany element nie jest też wartością wartownika to program sie zapętli. Powinno być w pierwszym przeszukiwaniu poza a=x? drugi warunek tj. a=wartownik? gdzie wartownik ustalony z góry jest liczbą inną z zakresu liczb w tablicy.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Tomasz Lubiński 2015-08-27 08:03
W tym podejściu nie ma opcji 'nie znajdzie szukanej'. Wartownik z definicji ma wartość szukanej liczby. Szukamy x, to wartownika ustawiamy na x przed rozpoczęciem szukania.

Ten algorytm to jest właśnie sprytne usprawnienie wyszukiwania poprzez sprawdzanie w każdej iteracji tylko jednego warunku (czy znaleziono szukany element) zamiast dwóch (czy znaleziono szukany element i czy nie doszliśmy do konca tablicy).
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz