algorytm.org

Szukanie zadanego elementu

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

Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej element 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].

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


Operację odnajdowania elementu w tablicy możemy zapisać następującym schematem blokowym:

schemat blokowy - szukanie elementu w tablicy


Algorytm ten ma 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.

Przykład:

Niech będzie dana tablica 5-elementowa, a = {4, 6, 2, 1, 3}.
Poszukajmy w niej element x = 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, zatem znaleźliśmy szukany element pod indeksem 3,
Poszukajmy teraz element x = 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,
To już koniec tablicy, zatem nie ma w niej elementu równego 5.

Przykład w JavaScript:


Podaj szukaną liczbę:



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 0
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 3
Albatross201C/C++C++ streams
.cpp
.cpp
***** / 1
MarianC/C++C++ streams, dynamiczna tablica elementów
.cpp
.cpp
***** / 1
Krzysztof SośnierzC/C++C++ templates
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 4
Adam ChrapkowskiHaskell
.hs
.hs
***** / 0
Tomasz LubińskiJava
.java
.java
***** / 3
Dominik GoździukJavaScript
.js
.js
***** / 0
Jakub KoniecznyJava_Block
.jbf
.jbf
***** / 0
Dominik GoździukPerl
.pl
.pl
***** / 1
Dominik GoździukPhp
.php
.php
***** / 0
Jakub KoniecznyPython
.py
.py
***** / 0
Nikodem SolarzRuby3 metody do szukania zadanego elementu w tablicy i zwracania indeksów
.rb
.rb
***** / 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: 04 marca 2012 15:08
Dodaj komentarz