Általános feladat: N elemű rendezett sorozat; egy keresett elem (X). Szerepel-e a keresett elem a sorozatban és ha igen, akkor mi a sorszáma.
Kihasználjuk, hogy a sorozat rendezett, így el tudjuk dönteni, hogy a keresett elem az éppen vizsgált elemhez képest hol helyezkedik el.
Al, F: intervallum alsó és felső végpontjai.
Eljárás: Al := 1 F := N Ciklus K := INT((Al + F) / 2) Ha A(K) < X akkor Al := K + 1 Ha A(K) > X akkor F := K - 1 amíg Al <= F és A(K) != X (amíg Al > F vagy A(K) = X) Ciklus vége VAN := Al <= F Ha VAN akkor SORSZ := K Eljárás vége.
Megjegyzés: azért hívják logaritmikus keresésnek, mert a ciklus lépésszáma kb. log N sokkal hatékonyabb rendezett sorozatra, mint a lineáris keresés.
Pascal forráskód
program binaris_logaritmikus_kereses; const n = 10; var a: array [1..n] of integer; i, j, c, x, als, fel, k: integer; van: boolean; begin randomize; //A tömb elkészítése for i:=1 to n do a[i]:=random(9); //Tömb rendezése for i:=1 to n-1 do for j:=i+1 to n do if a[j]<a[i] then begin c:=a[j]; a[j]:=a[i]; a[i]:=c; end; //A rendezett tomb kiiratasa for i:=1 to n do write(a[i], ' '); Writeln; //Binaris kereses als:=1; fel:=n; x:=random(11); writeln('a keresett elem: ', x); repeat k:=(als+fel) div 2; if a[k]<x then als:=k+1; if a[k]>x then fel:=k-1; until (als>fel) or (a[k]=x); van:=als<=fel; if van then writeln('megtalaltam, a sorszama: ', k) else writeln('nincsen meg'); readln; end.
A <binaris_logaritmikus_kereses.pas> forráskódjának futtatása online
Órai gyakorlat
program logaritmikus_kereses; const n=8; var i,j,al,fel,keresendo,koz, cs : integer; van:boolean; a: array [1..n] of integer; begin writeln('Kerem a tomb elemeit: '); for i:=1 to n do begin write('a[',i,'] = '); readln(a[i]); end; for i:=1 to n-1 do for j:=i+1 to n do if a[j]<a[i] then begin cs:=a[j]; a[j]:=a[i]; a[i]:=cs; end; write('A rendezett tomb elemei: '); for i:=1 to n do write(a[i]:3); writeln; //logaritmikus kereses al:=1; fel:=n; write('A keresendo szam: '); readln(keresendo); repeat koz := (al+fel) div 2; if a[koz]<keresendo then al:=koz+1; if a[koz]>keresendo then fel:=koz-1; until (al>fel) or (a[koz]=keresendo); van := al<=fel; if van then write('Megvan, sorszama: ',koz)else write('Nincs meg'); readln; end.