Zobrazenie zdroja stránky 9.Prednaska

{{Nadpis0nu|9. Prednáška|8.Prednaska|10.Prednaska}}

<!-- niekde dorobit WITH !!!! -->

== Typ záznam ==

Typ záznam je ďalší štruktúrovaný typ, ktorý definujeme sami. Pripomeňme si typ pole: je to skupina nejako očíslovaných prvkov (premenných), ktoré sú všetky rovnakého typu, napr. 100-prvkové pole reťazcov, alebo 10000-prvkové pole znakov, alebo 7-prvkové pole textových súborov a pod. Takáto štruktúra má svoje meno (meno poľa) a k prvkom pristupujeme cez '''''index''''' (nejaký ordinálny typ, najčastejšie je to interval celých čísel).

Záznam je tiež skupina premenných, ktoré ale nemusia byť rovnakého typu. K prvkom záznamu (budeme hovoriť '''''položky''''') budeme pristupovať cez ich meno. Pozrime si to na príklade. Najprv všeobecná konštrukcia definície záznamu

{{Prog}}
 {{Blue|type}}
   ''meno typu'' {{=}} {{Blue|record}}
     ''meno položky'':  ''typ položky'';
     ''meno položky'':  ''typ položky'';
     ...
   {{Blue|end}};
|}

Teraz niekoľko definícií typov:
 type
   TBod = record
     X, Y: Integer;
   end;
 &nbsp;
   TStudent = record
     Meno: string;
     Adresa: string;
     Rocnik: Byte;
     Priemer: Real;
   end;
 &nbsp;
   TSprite = record
     Pozicia: TBod;
     Faza: 0..3;
     Bmp: array [0..3] of TBitmap;
   end;
   
Prvým definovaným novým typom je tu '''TBod'''. Tento typ sa skladá z dvoch celočíselných premenných '''X''' a '''Y''' a preto bude v pamäti zaberať 8 bajtov.
:{{Obr|P9.1.png|140px|TBod v pamäti}}

Druhým novým typom je záznam '''TStudent''', ktorý sa skladá zo štyroch položiek (premenných). Prvé dve položky sú znakové reťazce, za tým je jednobajtové celé číslo a na koniec je to jedno desatinné číslo. Keby sme pomocou '''SizeOf()''' ziťovali, koľko pamäte zaberá takýto typ, tak dostaneme hodnotu 24. Hoci v pamäti je to uložené takto:
: obrázok rámik, v ktorom sú pod sebou ďalšie rámiky ...
a hodnota 24 vyplýva z toho, na aké adresy sa ukladajú desatinné čísla (vždy je to adresa deliteľná číslom 8, takže medzi premennou '''Rocnik''' a '''Priemer''' je 7 nevyužitých bajtov)
:{{Obr|P9.2.png|170px|TStudent v pamäti}}

Typ '''TSprite''' obsahuje položku '''Pozicia''', ktorá je opäť záznamom. Položka '''Bmp''' je zase 4-prvkové pole.
:{{Obr|P9.3.png|330px|TSrite v pamäti}}

Identifikátory položiek musia spĺňať kritériá nových identifikátorov (nesmú začínať číslicou, musia sa líšiť od rezervovaných slov a pod.), ale sú to "súkromné" premenné záznamu a preto sa neprekrývajú s menami iných premenných, podprogramov, typov, ...

So záznamom pracujeme buď ako s celkom (celou skupinou položiek), napr. pri priraďovaní jednej premennej do inej, alebo pri posielaní ako parameter podprogramu a pod. Alebo môžeme pracovať so samostatnými položkami ako s obyčajnými premennými. Ukážeme to na príklade:
 type
   TStudent = record
     Meno: string;
     Adresa: string;
     Rocnik: Byte;
     Priemer: Real;
   end;
 &nbsp;
 var
   Student, Spoluziak: TStudent;
 begin
   Student.Meno := 'Janko Hrasko';
   Student.Adresa := 'Mlyny';
   Student.Rocnik := 1;
   Student.Priemer := 1.23;
 &nbsp;
   Spoluziak := Student;
   Spoluziak.Meno := 'Jurko Fazulka';
 &nbsp;
 end;
V príklade vidíme, že k položkám pristupujeme pomocou bodkového zápisu: za premennú typu záznam zapíšeme bodku a za tým meno položky. Malo by vám to pripomínať, napr. prácu s rôznymi nastaveniami pre '''Canvas''' (napr. '''Canvas.Brush''', '''Pen.Color''', ...), alebo s nastaveniami pre bitmápy (napr. '''Obrazok.Width := 100'''). Princíp je rovnaký, len grafické časti a bitmapy sú objekty, ktoré sú trochu zložitejšie ako záznamy. V príklade sme najprv priradili nejaké hodnoty do všetkých položiek záznamu '''Student''', potom sme celý tento záznam priradili (skopírovali) do ďalšej záznamovej premennej '''Spoluziak'''. Na záver sme spolužiakovi zmenili '''Meno''', pričom '''Adresa''', '''Rocnik''' a '''Priemer''' ostali rovnaké ako v zázname '''Student'''.

V ďalšom príklade ukážeme, ako sa záznamy používajú v procedúrach a funkciách:
 type
   TBod = record
     X, Y: Integer;
   end;
 &nbsp;
 function BodToStr(B: TBod): string;
 begin
   Result := Format('(%d, %d)', [B.X, B.Y]);
 end;
 &nbsp;
 procedure Posun(var B: TBod; DX, DY: Integer);
 begin
   Inc(B.X, DX);   ''// B.X := B.X + DX;''
   Inc(B.Y, DY);
 end;
 &nbsp;
 function Bod(NoveX, NoveY: Integer): TBod;
 begin
   Result.X := NoveX;
   Result.Y := NoveY;
 end;
 &nbsp;
 var
   A, B, C: TBod;
 begin
   A.X := 100;
   A.Y := 200;
   B := {{Red|Bod(50, 150)}};
   C := A;
   Posun(C, 20, -15);
   WtiteLn('C = ', {{Red|BodToStr(C)}});

V príklade sme zadefinovali tri podprogramy, ktoré pracujú so záznamom '''TBod'''. Funkcia '''BodToStr''' zo záznamu vyrobí znakový reťazec. Procedúra '''Posun''' zmení v zázname obe súradnice. Funkcia '''Bod''' z dvoch celých čísel vyrobí záznam.


== Príklad s mestami na mape ==

Budeme riešiť príklad, v ktorom budeme klikať do obrázku mapy Slovenska na miesta, kde sa nachádzajú mestá. Informácie o týchto mestách (meno a pozíciu) budeme ukladať do poľa. Každým prvkom poľa bude štruktúra záznam s položkami '''Meno''' a '''X''' a '''Y'''. Do grafickej plochy vložíme obrázok mapy Slovenska zo súboru [[Media:Mapa.bmp|mapa.bmp]]: v inšpektore objektov dvojklikneme na nastavenie '''Picture''' a v dialógu nastavíme práve tento súbor:
: {{Obr|p9.4.png|270px|dialóg na vloženie bitmapy do grafickej plochy}} {{Obr|p9.5.png|310px|vyberieme súbor}} {{Obr|p9.6.png|270px|potvdíme}}
Do grafickej plochy vložíme aj vstupný riadok '''Edit1''', napr. takto
: {{Obr|p9.7.png|320px|formulár}}
Pripravíme procedúry pre udalosti '''Form1Create''' (dvojklikneme do formuláru mimo komponentov) a '''Image1MouseDown''' (cez inšpektor objektov). Prvá verzia našej aplikácie môže vyzerať takto:
 {{Red|type}}
   {{Red|TMesto {{=}} record}}
     {{Red|X, Y: Integer;}}
     {{Red|Meno: string;}}
   {{Red|end;}}
 &nbsp;
 procedure KresliMesto({{Red|M: TMesto}}; C: TCanvas);
 begin
   C.Pen.Color := clBlue;
   C.Pen.Width := 3;
   C.Ellipse(M.X - 5, M.Y - 5, M.X + 5, M.Y + 5);
   c.Font.Height := 20;
   C.TextOut(M.X, M.Y, M.Meno);
 end;
 &nbsp;
 var
   Mesto: array [1..1000] of {{Red|TMesto}};     ''// zoznam miest''
   N: Integer;                                   ''// momentálny počet miest''
 &nbsp;
 procedure TForm1.FormCreate(Sender: TObject);
 begin
   N := 0;
   Edit1.Text := '';
 end;
 &nbsp;
 procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
   Shift: TShiftState; X, Y: Integer);
 begin
   Inc(N);
   Mesto[N].X := X;
   Mesto[N].Y := Y;
   Mesto[N].Meno := Edit1.Text;
   Edit1.Text := '';
   KresliMesto(Mesto[N], Image1.Canvas);
 end;
Ako to funguje: po naštartovaní programu sa objaví mapa. Keď chceme pridať nejaké mesto, najprv do vstupného riadka napíšeme jeho meno (napr. Zvolen) a potom klikneme na miesto, kde sa má toto mesto vyznačiť (na bod so Zvolenom). Na príslušnom mieste sa nakreslí modrý krúžok a aj meno mesta. Procedúra '''Image1MouseDown''' zvýši počet miest , na posledné miesto v zozname miest (t.j. do premennej '''Mesto[N]''') vloží súradnice a meno mesta a toto mesto nakreslí do mapy.

Zrejme pri každom spustení programu musíme zadávať všetky mestá od začiatku, lebo program si ich nikde nepamätá. Využijeme na to textový súbor '''"slovensko.txt"''', do ktorého sa automaticky pri štarte programu prečíta zoznam miest a pri končení programu sa momentálny zoznam miest zapíše do tohto súboru. Okrem toho dorobíme ešte jednu udalosť: keď zapíšeme nejaký text do '''Edit1''' (teda meno nejakého mesta) a zatlačíme kláves <Enter>, udalosť '''Edit1KeyPress''' (vyberieme ju v inšpektore objektov v záložke '''Udalosti''' pre komponent '''Edit1''') zapíše toto meno k posledne vytváranému mestu (v premennej '''Mesto[N]'''). Vďaka tomuto, ak pri kliknutí zabudneme vložiť meno mesta, tak <Enter> vo vstupnom riadku toto meno doplní dodatočne.

Už vieme, že udalosť '''FormCreate''' sa automaticky spúšťa pri štarte programu (ešte pred zobrazením formulára). Sem zapíšeme kód, ktorý prečíta textový súbor, informácie z neho zapíše do poľa záznamov '''Mesta''' a tieto mestá aj vykreslí do mapy. Pri čítaní využijeme pomocnú funkciu '''CitajMesto''', ktorá z jedného riadku súboru prečíta informácie a vráti to ako výsledok funkcie, teda záznam typu '''TMesto'''.

K procedúre '''FormCreate''' existuje analogická procedúra '''FormDestroy''', ktorá sa spúšťa pri udalosti '''onDestroy''' - vtedy, keď sa aplikácia končí. Túto procedúru vytvoríme v inšpektore objektov na komponente '''Form1''' v záložke Udalosti, dvojklikneme v riadku '''onDestroy'''.

Kompletný projekt teraz vyzerá takto:
 type
   TMesto = record
     X, Y: Integer;
     Meno: string;
   end;
 &nbsp;
 procedure KresliMesto(M: TMesto; C: TCanvas);
 begin
   C.Pen.Color := clBlue;
   C.Pen.Width := 3;
   C.Ellipse(M.X - 5, M.Y - 5, M.X + 5, M.Y + 5);
   c.Font.Height := 20;
   C.TextOut(M.X, M.Y, M.Meno);
 end;
 &nbsp;
 {{Red|function CitajMesto(var T: TextFile): TMesto;}}
 var
   Z: Char;
 begin
   Result.Meno := '';
   Read(T, Z);
   while Z <> ';' do
   begin
     Result.Meno := Result.Meno + Z;
     Read(T, Z);
   end;
   ReadLn(T, Result.X, Result.Y);
 end;
 &nbsp;
 var
   Mesto: array [1..1000] of TMesto;
   N: Integer;
 &nbsp;
 procedure TForm1.FormCreate(Sender: TObject);
 var
   T: TextFile;
   I: Integer;
 begin
   N := 0;
   Edit1.Text := '';
   if FileExists('slovensko.txt') then         ''// funkcia zistí, či takýto súbor už existuje''
   begin
     AssignFile(T, 'slovensko.txt');
     Reset(T);
     while not Eof(T) do
     begin
       Inc(N);
       Mesto[N] := {{Red|CitajMesto(T)}};
       KresliMesto(Mesto[N], Image1.Canvas);
     end;
     CloseFile(T);
   end;
 end;
 &nbsp;
 {{Red|procedure TForm1.FormDestroy(Sender: TObject);}}
 var
   T: TextFile;
   I: Integer;
 begin
   AssignFile(T, 'slovensko.txt');
   Rewrite(T);
   for I := 1 to N do
     WriteLn(T, Mesto[I].Meno, ';', Mesto[I].X, ' ', Mesto[I].Y);
   CloseFile(T);
 end;
 &nbsp;
 {{Red|procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: char);}}
 begin
   if (Key = #13) and (N > 0) and (Edit1.Text <> '') then
   begin
     Mesto[N].Meno := Edit1.Text;
     Edit1.Text := '';
     KresliMesto(Mesto[N], Image1.Canvas);
   end;
 end;
 &nbsp;
 procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
   Shift: TShiftState; X, Y: Integer);
 begin
   Inc(N);
   Mesto[N].X := X;
   Mesto[N].Y := Y;
   Mesto[N].Meno := Edit1.Text;
   Edit1.Text := '';
   KresliMesto(Mesto[N], Image1.Canvas);
 end;

Ešte niekoľko poznámok k projektu:
* funkcia '''CitajMesto''' číta reťazec '''Meno''' po znakoch, lebo čítať musíme len po prvý výskyt znaku ';'
** ak by sme to chceli prečítať napr. takto '''ReadLn(T, Result.Meno, Result.X, Result.Y);''' spadlo by to na chybovej správe
* vo '''FormCreate''' používame štandardnú funkciu '''FileExists''', ktorá vie zistiť, či súbor, ktorý chceme otvoriť, už existuje
** keby tu tento test nebol a textový súbor by ešte neexistoval, program by spadol pri otváraní príkazom '''Reset(T)'''
* nová procedúra '''FormDestroy''' sa automaticku spustí, keď bežiacu aplikáciu ukončíme korektne (napr. Alt-F4), keď ju ukončíme z prostredia Lazarus tlačidlom '''Zastaviť''' (alebo Ctrl-F2), '''FormDestroy''' sa nespustí, teda neuloží prípadné nové mestá


== Príklad s poľom bodov ==

Zadefinujme nový typ '''TPoint''', ktorý bude reprezentovať bod v grafickej ploche.
 type
   {{Red|TPoint {{=}} record}}
     X, Y: Integer;
   end;
 &nbsp;
 function Point(X, Y: Integer): TPoint;
 begin
   Result.X := X;
   Result.Y := Y;
 end;
 &nbsp;
 var
   XY: array [1..100000] of TPoint;
   N: Integer;
Zároveň s týmto novým typom zadefinujeme pole '''XY''', do ktorého budeme ukladať postupnosť bodov v rovine. V premennej '''N''' si budeme pamätať momentálny počet bodov v tomto poli, na začiatku je '''N = 0''', nový bod do tohto zoznamu pridávame za doteraz uložené, t.j. '''XY[N+1]'''. Nový bod budeme teda pridávať do tohto poľa takto:
   Inc(N);
   XY[N] := Point(nejakeX, nejakeY);

Napíšeme program, v ktorom budeme kresliť do grafickej plochy ťahaním myši. Pritom sa budú všetky body, ktoré prídu z udalostí '''Image1MouseDown''' a '''Image1MouseMove''' ukladať do poľa '''XY'''. Procedúra '''Image1MouseUp''' (ktorá sa zavolá pri udalosti '''onMouseUp''', t.j. pri pustení tlačidla myši) by mohla s týmto poľom bodov robiť rôzne akcie. Napr.
* uložiť tento zoznam do súboru,
* uložiť zoznam do nejakej dátovej štruktúry,
* prekresliť túto krivku s nejakými novými parametrami;
* nejako spracovať tento zoznam matematickými operáciami (napr. zmenšovať, otáčať, ...)

Ukážeme program, v ktorom pri pustení myši sa kresba prekreslí hrubšou čiarou náhodnou farbou:
 type
   {{Red|TPoint {{=}} record}}
     X, Y: Integer;
   end;
 &nbsp;
 function Point(X, Y: Integer): TPoint;
 begin
   Result.X := X;
   Result.Y := Y;
 end;
 &nbsp;
 var
   XY: array [1..100000] of TPoint;
   N: Integer;
 &nbsp;
 procedure TForm1.FormCreate(Sender: TObject);
 begin
   Image1.Canvas.FillRect(Image1.ClientRect);
 end;
 &nbsp;
 procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;
   Shift: TShiftState; X, Y: Integer);
 begin
   Image1.Canvas.Pen.Color := clBlack;
   Image1.Canvas.Pen.Width := 1;
   Image1.Canvas.MoveTo(X, Y);
   N := 1;
   XY[N] := Point(X, Y);
 end;
 &nbsp;
 procedure TForm1.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
   Y: Integer);
 begin
   if Shift = [ssLeft] then
   begin
     Image1.Canvas.LineTo(X, Y);
     Inc(N);
     XY[N] := Point(X, Y);
   end;
 end;
 &nbsp;
 procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
   Shift: TShiftState; X, Y: Integer);
 var
   I: Integer;
 begin
   if N > 0 then
   begin
     Image1.Canvas.Pen.Color := Random($1000000);  ''// to isté ako Random(256 * 256 * 256)''
     Image1.Canvas.Pen.Width := 3;
     Image1.Canvas.MoveTo(XY[1].X, XY[1].Y);
     for I := 2 to N do
       Image1.Canvas.LineTo(XY[I].X, XY[I].Y);
   end;
   N := 0;
 end;

Pozrime si deklaráciu nášho nového typu '''TPoint'''. Hoci sme ho definovali na začiatku nášho programu, túto deklaráciu môžeme úplne vyhodiť, keďže úplne rovnako definovaný typ je aj v štandardnej knižnici Pascalu. Taktiež funkcia '''Point''', ktorá ako výsledok vracia záznam typu '''TPoint''' je definovaná už v štandardnej knižnici a preto jej definíciu môžeme z programu vyhodiť. Ak to vyskúšate (vyhodíte deklaráciu '''TPoint''' aj funkciu '''Point'''), program normálne funguje.

Vyhodenie deklarácie '''TPoint''' má ešte jeden užitočný dôsledok: grafické príkazy '''Polyline''' a '''Polygon''' očakávajú ako parameter ľubovoľné pole, ktorého prvkami sú '''TPoint'''. Ale nie ten náš pôvodný '''TPoint''', ale len ten štandardný. Preto, namiesto for-cyklu, pomoocu ktorého sme vykresľovali lomenú čiaru v poli '''XY''', môžeme použiť '''Polyline''' (s úplne rovnakým efektom):
 procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
   Shift: TShiftState; X, Y: Integer);
 {{Comm|//var}}
 {{Comm|//  I: Integer;}}
 begin
   if N > 0 then
   begin
     Image1.Canvas.Pen.Color := Random($1000000);
     Image1.Canvas.Pen.Width := 3;
     {{Red|Image1.Canvas.Polyline(XY[1..N]);}}
     {{Comm|//Image1.Canvas.MoveTo(XY[1].X, XY[1].Y);}}
     {{Comm|//for I :{{=}} 2 to N do}}
     {{Comm|// Image1.Canvas.LineTo(XY[I].X, XY[I].Y);}}
   end;
   N := 0;
 end;
Všimnite si skutočný parameter pri volaní '''Polyline''': hoci parametrom má byť pole bodov '''TPoint''', teda napr. '''Image1.Canvas.Polyline(XY);''', my ale nechceme vykresľovať celý obsah poľa '''XY''' (10000 prvkov), ale len prvých '''N'''. Preto môžeme zapísať '''Image1.Canvas.Polyline({{Red|XY[1..N]}});'''

Keď nahradíme volanie '''Polyline''' volaním '''Polygon''', tak kreslená lomená čiara ohraničuje oblasť, ktorá sa vyplní farbou štetca. Procedúru '''Image1MouseUp''' môžeme zapísať takto:
 procedure TForm1.Image1MouseUp(Sender: TObject; Button: TMouseButton;
   Shift: TShiftState; X, Y: Integer);
 begin
   if N > 0 then
   begin
     Image1.Canvas.Pen.Color := Random($1000000);
     Image1.Canvas.Pen.Width := 3;
     {{Red|Image1.Canvas.Polygon(XY[1..N]);}}
   end;
   N := 0;
 end;


== Príkaz with ==


Príkaz '''with''' umožňuje pristupovať k prvkom záznamu (alebo objektu) bez toho, aby sme zakaždým museli uvádzať meno premennej (resp. objektu). Syntax príkazu je
{{Prog}}
 {{Blue|with}} ''premenná'' {{Blue|do}}
   ''príkaz'';
|}
Premenná musí byť typu záznam (objekt). V tele príkazu sa potom všetky premenné skontrolujú, či nie sú položkami tohto záznamu. Ak nie sú, tak zrejme to budú "obyčajné" premenné. Ak máme deklarácie
 type
   TStudent = record
     Meno: string;
     Adresa: string;
   end;
 var
   Prvak: TStudent;
nasledovné príkazy budú ekvivalentné:
 Prvak.Meno := ’Tomas’;
 Prvak.Adresa := ’Kosice’;
s týmto zápisom
 {{Blue|with}} Prvak do
 begin
   Meno := ’Tomas’;
   Adresa := ’Kosice’;
 end;

Príkazy '''with''' môžu byť vnorené, napr.
{{Prog}}
 {{Blue|with}} ''premenná<sub>1</sub>'' {{Blue|do}}
   {{Blue|with}} ''premenná<sub>2</sub>'' {{Blue|do}}
     ''príkaz'';
|}
môžeme to skrátene zapísať aj takto:
{{Prog}}
 {{Blue|with}} ''premenná<sub>1</sub>'', ''premenná<sub>2</sub>'' {{Blue|do}}
   ''príkaz'';
|}

Príkaz '''with''' môžeme využiť aj pri kreslení. Grafická plocha '''Image1''', plátno '''Canvas''' ale napr. aj štetec '''Brush''' sú objekty a preto môžeme využiť '''with'''. Takýto zápis
 Image1.Canvas.Brush.Color := clYellow;
 Image1.Canvas.Brush.Style := bsSolid;
 Image1.Canvas.Rectangle(0, 100, 50, 200);
Môžeme prepísať
 {{Blue|with}} Image1.Canvas do
 begin
   Brush.Color := clYellow;
   Brush.Style := bsSolid;
   Rectangle(0, 100, 50, 200);
 end;
ale aj
 {{Blue|with}} Image1.Canvas do
 begin
   {{Blue|with}} Brush do
   begin
     Color := clYellow;
     Style := bsSolid;
   end;
   Rectangle(0, 100, 50, 200);
 end;
ale aj
 {{Blue|with}} Image1.Canvas, Brush do
 begin
   Color := clYellow;
   Style := bsSolid;
   Rectangle(0, 100, 50, 200);
 end;

Tento príkaz niektorí programátori neobľubujú, lebo niekedy je tu nemalé riziko, že to Pascal pochopí inak, ako sme zamýšľali, hlavne pri vnorených príkazoch '''with'''.

<!-- -->

== Hľadanie v poli ==


Predpokladajme, že máme nejaké veľké pole celých čísel, v ktorom máme nájsť nejakú konkrétnu hodnotu. Hoci v praxi by sme skôr prehľadávali pole, napr. znakových reťazcov, alebo pole záznamov, my si to zjednodušíme na pole celých čísel.
 type
   TPole = array [1..100000] of Integer;
 var
   Pole: TPole;
   N: Integer;

Pole môžeme zaplniť náhodnými hodnotami, napr. takto:
 N := High(Pole);
 for I := 1 to N do
   Pole[I] := Random(MaxInt);

Nasledujúca funkcia zisťuje, či sa nejaká hodnota v tomto poli nachádza a ak áno, vráti index tohto prvku v poli. Inak vráti hodnotu 0:
 function Hladaj(Hodnota: Integer): Integer;
 begin
   Result := 1;
   while (Result <= N) and (Pole[Result] <> Hodnota) do
     Inc(Result);
   if Result > N then
     Result := 0;
 end;
Ak hľadáme hodnotu, ktorá sa v poli nenachádza, tak ju musíme porovnať so všetkými hodnotami v poli. Teda vtedy while-cyklus prejde '''N'''-krát.

Algoritmus hľadania môžeme trochu vylepšiť, ak budeme predpokladať, že pole je vzostupne utriedené (zrejme ho nemôžeme vytvárať hore uvedeným for-cyklom). Vylepšená verzia hľadania:
 function Hladaj(Hodnota: Integer): Integer;
 begin
   Result := 1;
   while (Result <= N) and (Pole[Result] < Hodnota) do
     Inc(Result);
   if (Result > N) {{Green|or (Pole[Result] <> Hodnota)}} then
     Result := 0;
 end;

Zistite, čo bude funkcia '''Hladaj''' vyhľadávať, ak z nej vyhodíme zeleným označenú časť.

Utriedenú pole môžeme prehľadávať aj od konca:
 function Hladaj(Hodnota: Integer): Integer;
 begin
   Result := N;
   while (Result > 0) and (Pole[Result] > Hodnota) do
     Dec(Result);
   if (Result <> 0) and (Pole[Result] <> Hodnota) then
     Result := 0;
 end;

Predpokladali sme, že pole je utriedené, napíšme procedúru '''Pridaj''', tak aby sa nová hodnota vkladala na správne miesto.
 procedure Pridaj(Hodnota: Integer);
 var
   I: Integer;
 begin
   I := N;
   while (I > 0) and (Pole[I] > Hodnota) do
   begin
     {{Red|Pole[I+1] :{{=}} Pole[I];}}
     Dec(I);
   end;
   Pole[I+1] := Hodnota;
   Inc(N);
 end;

While-cyklus tu posunie prvky poľa tak, aby sa nová hodnota mohla zasunúť na správne miesto. Zrejme predpokladáme, že zaraďovaná hodnota sa ešte v poli nenachádza.

{{Podnadpis|Binárne vyhľadávanie}}

Naučíme sa nový typ algoritmu, tzv. '''binárne vyhľadávanie'''. Je podobný tomu, ako keď hľadáme v telefónnom zozname:
* otvoríme približne v strede zoznamu: ak je hľadané slovo v abecede skôr ako slovo v strede telefónneho zoznamu, tak budeme pokračovať v prednej v jeho polovici, inak v druhej polovici,
* opäť vo vybranej polovici zoznamu sa pozrieme do jeho stredu a porovnáme s hľadaným slovom: ak je v abecede skôr, budeme pokračovať v prvej časti, inak v druhej,
* takto budeme postupne hľadať v menšom a menšom úseku zoznamu, až kým nenarazíme na hľadané slovo.

Treba si zapamätať, že to funguje, len ak je pole, resp. tabuľka utriedená:
 function Hladaj(Hodnota: Integer): Integer;
 var
   Zac, Kon, Stred: Integer;
 begin
   Zac := 1;                          {{Comm|// začiatok intervalu}}
   Kon := N;                          {{Comm|// koniec intervalu}}
   while Zac <= Kon do
   begin
     Stred := (Zac + Kon) div 2;      {{Comm|// stred intervalu}}
     if Pole[Stred] < Hodnota then
       Zac := Stred + 1
     else if Pole[Stred] > Hodnota then
       Kon := Stred - 1
     else
       Zac := K + 1;                  {{Comm|// našiel}}
   end;
   if Pole[Stred] = Hodnota then
     Result := Stred
   else
     Result := 0;
 end;

alebo ešte iné riešenie, ktoré využije vyskočenie z podprogramu pomocou príkazu '''Exit''':
 function Hladaj(Hodnota: Integer): Integer;
 var
   Zac, Kon: Integer;
 begin
   Zac := 1;
   Kon := N;
   while Zac <= Kon do
   begin
     Result := (Zac + Kon) div 2;
     if Pole[Result] = Hodnota then
       {{Red|Exit}};
     if Pole[Result] < Hodnota then
       Zac := Result + 1
     else
       Kon := Result - 1;
   end;
   Result := 0;
 end;

Príkaz '''Exit''' neukončí vykonávanie celého programu, ale len podprogramu, v ktorom sa nachádza. Ak vyskakujeme z funkcie, zrejme ešte pred príkazom '''Exit''' treba priradiť do '''Result''' výslednú hodnotu funkcie.

Ďalšie informácie o tomto vyhľadávaní si môžete pozrieť na stránkach [http://sk.wikipedia.org/wiki/Binárne_vyhľadávanie sk.wikipedia] alebo [http://en.wikipedia.org/wiki/Binary_search_algorithm en.wikipedia]

== Meranie rýchlosti vyhľadávania ==


Použitím štandardných podprogramov '''Now''' (vráti momentálny dátum a čas v počítači s presnosťou na tisíciny sekundy) a '''DecodeTime''' (dekóduje takto získaný čas na hodiny, minútu, sekundy a milisekundy) môžeme dosť presne odmerať, ako dlho bežal nejaký výpočet. (Keďže pracujeme v konzolovom režime, musíme do riadku '''uses''' pridať aj '''SysUtils''') Budeme to organizovať napr. takto:
 uses
   Classes, SysUtils;
 &nbsp;
 function Cas(C: TDateTime): string;
 var
   Hod, Min, Sek, Msek: Word;
 begin
   DecodeTime(C, Hod, Min, Sek, Msek);
   Result := Format('%d:%.2d:%.2d:%.3d', [Hod, Min, Sek, Msek]);
 end;
 &nbsp;
 var
   ZapamatanyCas: TDateTime;
 begin
 &nbsp;
   {{Red|ZapamatanyCas :{{=}} Now;}}                               {{Comm|// zapamätá si momentálny čas}}
   WriteLn('start o ', Cas(ZapamatanyCas));
 &nbsp;
   {{Comm|// výpočet, ktorý potrebujeme odmerať}}
 &nbsp;
   WriteLn('testovanie trvalo ', Cas({{Red|Now - ZapamatanyCas}}));     {{Comm|// výpis času}}
   ReadLn;
 end.

Vyhľadávania môžeme otestovať napr. takto:
 var
   Pole: array [1..10000000] of Integer;
 &nbsp;
 function Hladaj1(Hodnota: Integer): Integer;
 begin
   Result := High(Pole);
   while (Result > 0) and (Pole[Result] <> Hodnota) do
     Dec(Result);
 end;
 &nbsp;
 function Hladaj2(Hodnota: Integer): Integer;
 begin
   Result := High(Pole);
   while (Result > 0) and (Pole[Result] > Hodnota) do
     Dec(Result);
   if (Result <> 0) and (Pole[Result] <> Hodnota) then
     Result := 0;
 end;
 &nbsp;
 function Hladaj3(Hodnota: Integer): Integer;
 var
   Zac, Kon: Integer;
 begin
   Zac := 1;
   Kon := High(Pole);
   while Zac <= Kon do
   begin
     Result := (Zac + Kon) div 2;
     if Pole[Result] = Hodnota then
       Exit;
     if Pole[Result] < Hodnota then
       Zac := Result + 1
     else
       Kon := Result - 1;
   end;
   Result := 0;
 end;
 &nbsp;
 const
   Pocet = 1000;   {{Comm|// Pocet {{=}} 10000000; pre binárne vyhľadávanie}}
 var
   ZapamatanyCas: TDateTime;
   I, Max: Integer;
 begin
   Randomize;
   Pole[1] := 1;
   for I := 2 to High(Pole) do
     Pole[I] := Pole[I-1] + Random(100) + 1;
   Max := Pole[High(Pole)] + 100;
 &nbsp;
   ZapamatanyCas := Now;
   WriteLn('startujem o ', Cas(ZapamatanyCas), ' pre ', Pocet, ' testov ... ');
   for I := 1 to Pocet do
     {{Green|Hladaj1(Random(Max));}}
 &nbsp;
   WriteLn('testovanie trvalo ', Cas(Now - ZapamatanyCas));
   ReadLn;
 end.

Postupne otestujeme rýchlosť vyhľadávania pre obyčajné sekvenčné ('''Hladaj1'''), sekvenčné v utriedenom poli ('''Hladaj2''') a binárne vyhľadávanie ('''Hladaj3'''). Pre Binárne vyhľadávanie zmeníme počet testov z 1000 na 10000000 (t.j. 10000-krát viac). V závislosti od kvality vášho počítača vám môžu vyjsť asi takéto výsledky:
<blockquote>
{| border="1"
| width="100" | ''algoritmus''
| width="100" | ''počet testov''
| width="100" | ''trvanie''
| width="100" | ''trvanie jedného''
|-
| '''Hladaj1''' || 1000 || 48 sek. || 0.048 sek.
|-
| '''Hladaj2''' || 1000 || 25 sek. || 0.025 sek
|-
| '''Hladaj3''' || 10000000 || 24 sek. || 0.0000024 sek
|}
</blockquote>

Otestujte a porovnajte to na vašom počítači. Vedeli by ste matematicky zdôvodniť, prečo je binárne vyhľadávanie v 10mld. prvkovom utriedenom poli asi 10000-krát rýchlejšie ako sekvenčné?

Poznámky:
* pole má 10M celých čísel, t.j. v pamäti zaberá 40MB,
* pole sa na začiatku vygenerovalo tak, aby bolo vzostupne utriedené - každý ďalší prvok sa vypočítal tak, že sa k predchádzajúcemu pripočítala nejaká malá náhodná hodnota,
* potom sa zapamätá momentálny čas (až na milisekundy), potom sa nejaký počet-krát (napr. 1000) spustí algoritmus hľadania s nejakými náhodnými hodnotami a na záver sa od momentálneho času odpočíta zapamätaný - tým dostaneme čas trvania 1000 spustení funkcie
** všimnite si, že hoci je '''Hladaj''' funkciou, volali sme ju ako keby bola procedúrou - toto si môžeme dovoliť vtedy, keď nám nevadí, že sa stratí výsledok funkcie


{{nav|8.Prednaska|10.Prednaska}}