10. astea | bilaketa bitarra array sailkatu/ordenatu batean

Bilaketa bitarraren zuhaitza osatzeko simuladorea

---

Enuntziatua

Demagun A bektorearen elementuak sailkaturik/ordenaturik daudela, gako ezagun bat zehaztu ondoren, balio hori aintzat harturik bektorea arakatu eta gakoarekin bat egiten duen lehen elementuari dagokion indizea aurkitu.

---

Ebazpena

Ebazpenak hiru urrats dituela onar daiteke.



Lehenengoan, bektorearen esparru baliagarria zehaztu behar da. asHiztegia bektorearen hasierako esparrua 1 behemuga eta iLuzera luzera efektiboaren bitartekoa izango da.



Ebazpenaren bigarren urratsean bektorearen esparru baliagarria erdibituz bi zatitan banatzen da, eta, esparruaren erdian dagoen elementuaren balioa gakoarekin alderaratzen da ondoko egoera bat gertatuz:

• asHiztegia[Erdi] = sGakoa, hots, berdinak izatea, bilatzen ari ginen gakoa A bektorean aurkitzen da eta berari dagokion posizioa esparruaren erdiko elementuaren indizearena da


• asHiztegia[Erdi] > sGakoa, hots, erdiko elementuaren balioa gakoa baino handiagoa bada, esparru baliagarria aldatu behar da: berria izango den esparruaren amaiera aurreko esparruaren erdia delarik (esparru berriaren hasiera ez da aldatzen). Beste modu batez esanda Eskn aldatu beharra dago


• asHiztegia[Erdi] < sGakoa, hots, erdiko elementuaren balioa gakoa baino txikiagoa bada, esparru baliagarria aldatu behar da ere, baina orain: berria izango den esparruaren hasiera aurreko esparruaren erdia izanik (esparru berriaren bukaera ez da aldatzen). Beste modu batez esanda Ezkr aldatu beharra dago

Hirugarren urratsak ebazpenaren bigarren urratseko prozesu errepikakorraren irteerako kondizioarekin zerikusia du. Begizta bukatzeko, bi baldintza hauetatik bat betetzea aski da:

1. bilaketa arrakastatsua: gakoa bektorean aurkitzea (esparru baliagarriaren erdiko elementuaren balioa eta gakoa berdinak direla frogatu da), edo bestela...


2. ...bilaketa okerra: gakoa ez dago bektorean (esparru baliagarriak ez du elementurik barneratzen, esparruak duen goimuga bere behemuga baino txikiagoa delako)

Algoritmo hau programatzeko WHILE-DO eta REPEAT-UNTIL kontrol-egiturak proposatzen ditugu, ezin daiteke inolaz ere FOR-TO-DO egitura erabili.

---

Kodea

...
readln(sGakoa) ;       { suposatuz sGakoa teklatuz irakurtzen dela }

boAurkitua := FALSE ;  { hasieran oraindik ez dugu sGakoa aurkitu }
iEzkr := 1 ;           { lehen indizea } 
iEskn := iLuzera ;     { luzera efektiboa } 
repeat
   iErdi := (iEzkr+iEskn) div 2 ;
   if asHiztegia[iErdi] = sGakoa then
      boAurkitua := TRUE
   else
      if asHiztegia[iErdi] > sGakoa then 
         iEskn := iErdi - 1
      else
         iEzkr := iErdi + 1 ;
until boAurkitua or (iEzkr > iEskn) ;

if boAurkitua then
   writeln(sGakoa, '-ren lehen agerpena ', iErdi, ' posizioan ematen da')
else
   writeln(sGakoa, ' ez da bektorean aurkitzen') ;
...

---

Eskema

Eskema hau jarraian datorren adibidearen exekuzio bati dagokio, kasu honetan yoyo gakoa ez da aurkituko:

Eskema hau adibidearen beraren beste exekuzio bati dagokio, kasu honetan uso gakoa aurkitu egingo da:

---

Adibidea: Hiztegia

Bektore bati esker hitzak gordeko ditugu memorian, bektoreari balioak ematean hitzen ordena alfabetikoa zainduko denez esan daiteke bektorea hiztegi bat dela.



Hiztegia datuz bete ondoren gako bat teklatuz irakurtzen da, adibide honetan gakoa hitz bat izango da noski.



Gakoaren lehen agerpena itzultzen duen funtzioak bilaketa bitarra darabil, gakoa bektorean aurkitzen denean funtzioak bere agerpen horri dagokion indizea itzuliko dio programa nagusiari, baina, gakoa bektorean ez dagoenaren egoera horretaz programa nagusia konturatu dadin funtzioak balio berezi bat itzultzen dio (posizioa ezin daitekeen izan balio berezia, adibidez 0).



Programa hauxe da:

08a_BilaketaBitarra.pas (hiztegia)

---

Adibidea: Ikasleak

31. taldeko ikasleen zerrenda asGela31 bektorean gorderik daukagu. Bektorean datuak gordetzean hasieraketa bat egiten da (datuak ez dira teklatuz ematen). Bektorea beti beterik dagoelako bere luzera efektiboa GOIMUGA da.



asGela31 bektorearen edukia pantailaru ondoren ikus daiteke datuak alfabetikoki ordenaturik daudela. Beraz, ikasle baten bilaketa egiteko bilaketa bitarra egingo da.



Programa hauxe da:

08b_BilaketaBitarra.pas (ikasleak)