ALG1
7.2. Przeszukiwanie binarne 191
Znalazlem=TAK;
else
if(tab[mić]<x)
loft-mid+1;
else
right=mid-l ;
)
if(Znalazlem==TAK) return mi ti; else return -1;
)
Nazwy i znaczenie zmiennych są dokładnie takie same. jak we wspomnianym zadaniu, dlatego warto tam zerknąć choć raz dla porównania. Pewnej dyskusji wymaga problem wyboru elementu „środkowego” (muf). W naszych przykładach jest to dosłownie środek aktualnie rozpatrywanego obszaru poszukiwań. W rzeczywistości jednak może nim być oczywiście dowolny indeks pomiędzy lej) i righl! Nietrudno jednak zauważyć, że „przepoławianie" tablicy zapewnia nam eliminację największego możliwego obszaru poszukiwań. Ich niepowodzenie jest sygnalizowane przez zwrot wartości -/. W przypadku sukcesu zwracany jest „tradycyjnie” indeks elementu w tablicy.
Przeszukiwanie binarne jest algorytmem klasy Ollog 2 N) (patrz Rozkład ..logarytmiczny”). Dla dokładnego uświadomienia sobie jego zalet weźmy pod uwagę konkretny przykład numeryczny:
Przeszukiwanie liniowe pozwala w czasie proporcjonalnym do rozmiaru tablicy (listy) odpowiedzieć na pytanie, czy element x się w niej znajduje. Zatem dla tablicy o rozmiarze 20,000 należałoby w najgorszym przypadku wykonać 20,000 porównań, aby odpowiedzieć na postawione pytanie. Analogiczny wynik dla przeszukiwania binarnego wynosi log 2 20000 (ok. 14 porównań)._
Nic tak dobrze nic przemawia do wyobraźni, jak dobrze dobrany przykład liczbowy, a powyższy na pewno do takich należy...
7.3.Transformacja kluczowa
Zanim powiemy choćby słowo na temat transformacji kluczowej, musimy sprecyzować dokładnie dziedzinę zastosowań tej metody. Otóż jest ona używana.
Wyszukiwarka
Podobne podstrony:
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa przeszukiwania
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa przeszukiwania
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa przeszukiwania
ALG1 Przedmowa 11 Początkującym zalecane jest trzymanie się porządku narzuconego przez układ rozdzi
ALG1 1.2. Jak to się niedawno odbyło, czyli. 211.2. Jak to się niedawno odbyło, czyli o tym kto „wy
ALG1 2.2. Ilustracja pojęcia rekurencji 31 od psychologii zachowań dziecka chwyciłby się za głowę z
ALG1 2.B. Typy programów rekurencyjnych 41 if (x==0) return 1; else return x*silnial !x-l); t Nie j
ALG1 i 2.10. Rozwiązania i wskazówki do zadań 51Zad. 2-3 Program nie należy do zbyt skomplikowanych
ALG1 3.2. Przykład 1: Jeszcze raz funkcja silnia... 61 W obliczeniach wykonywanych przez programist
ALG1 3.7. Analiza programów rekurencyjnych 71 Cały ten bagaż wzorów był naprawdę niezbędny! Dla zil
ALG1 Rozdział 4Algorytmy sortowania Tematem tego rozdziału będzie opis kilku bardziej znanych metod
ALG 1 4.4. Uwagi praktyczne 91 4.4. Uwagi praktyczne 91 quick-gcc.cc int comp(const void *x, const v
ALG1 5.1 Listy jednokierunkowe 101 5.1 Listy jednokierunkowe 101 ELEMENT Aprzed=NULL,*po=inf.głowa;
ALG1 5.1. Listy jednokierunkowe 111 i zarobków. (Rozbudowa tych struktur danych nie wniosłaby konce
ALG1 5.1 Listy jednokierunkowe 121 } cout << "
ALG1 5.3. Stos 131 Idea klasy szablonowej polega na stworzeniu wzorcowego kodu, w którym typ pewnyc
ALG1 5.5. Sterty i kolejki priorytetowe 141 Treść procedury DoGory nie powinna stanowić niespodzian
ALG1 5.6. Drzewa i ich reprezentacje 151 Jak łatwo zauważyć, w zależności od sposobu przechadzania
ALG1 5.8. Zbiory 161 sl=sł- C ; cout « "Zbiór SI - C = "; sl .pisz () ; cout << &
więcej podobnych podstron