SEM INF 8.12.2010

Hľadanie

Je to vlaste prehľadávanie poľa za účelom zistenia, či sa hľadaný prvok v poli nachádza alebo nie. Rozlišujú sa dva typy, podľa toho či je pole usporiadané alebo nie:

 I.    Lineárne
        Používa sa, ak je pole neusporiadané. Vtedy postupne od 1. až po posledný prvok zisťujeme, či je to hľadaný prvok.

II.    Binárne
        Používa sa v usporiadanom poli. Najprv pozrieme do prostriedku poľa, a zistíme či je prvok väčší alebo menší ako hľadaný prvok, podľa toho sa pozrieme do polky tej prislúchajucej časti, kde by sa hľadaný prvok mal nachádzať. A tak ďalej, až kým ho nenájdeme.

Program: binárne vyhľadávanie:
    pre zadané pole, ktoré je usporiadané vzostupne:

***

 program binarne_hladanie;
{Toto je pre pole, ktore je na zaciatku usporiadane vzostupne}
uses crt;
var n,i,hh,dh,s,h: integer;
a: array [1..1000] of integer;
begin
  clrscr;
  write('Zadaj pocet prvkov pola: '); readln(n);
  write('Zadaj pole (usporiadanie vzostupne): ');
  for i:=1 to n do
    read(a[i]);
  readln;
  write('Zadaj prvok ktory chces v poli najst: ');
  readln(h);
  if h>a[n] then writeln('nie')
  else begin
    hh:=a[n];
    dh:=a[1];
    s:=n+1;
    a[s]:=n+1;
    while (a[s]<>h) and (dh<=hh) do begin
      s:=(dh+hh) div 2;
      if a[s] > h then hh:=s-1
      else dh:=s+1;
    end;
    if a[s]=h then writeln('ano')
    else writeln('nie');
  end;
  readln;
end.

***

Tento program je tu.
Aplikácia je tu.
Tento program pracoval na princípe: pozrie sa do stredu poľa, ak hľadaný je menší ako to, tak sa na tú druhú polku poľa vykašle, a pozerá sa už iba do tej menšej. A to stále opakuje, potom sa pozrie do polky, zistí či je menší alebo väčší, potom sa pozrie do tej polky, kde by ten prvok poľa mal byť,a to robí až kým ten prvok nenájde, alebo kým sa už nemá kde pozrieť. 

Koniec hodiny.