Määritys - menetelmä - toteutus (jatkuu)
Toinen esimerkki: tiedonhaku järjestetystä listasta.
Määritys:
- syöte: jono suuruusjärjestyksessä annettuja kokonais-lukuja a1 £ a2 £ ... £ aN ja luku x.
- tulos: vastaus kysymykseen ”esiintyykö luku x jonossa a1,a2, ..., aN, so. onko x = ai jollakin i = 1,…, N?”
- huom: kokonaislukulistan sijaan voitaisiin tarkastella mitä tahansa järjestettyä luetteloa, vaikkapa henkilön x etsimistä puhelinluettelosta, johon sisältyvät nimet ovat aakkosjärjestyksessä a1,a2, ..., aN.
Menetelmä 1: peräkkäishaku.
- Vertaa lukua x lukuun a1:
- jos x = a1, tulos on ”löytyi”;
- jos x < a1, tulos on ”ei löytynyt”;
- jos x > a1, jatka listan läpikäyntiä.
- Toista askel 1 listan alkioilla a2, ..., aN.
- Jos lopulta x > aN, tulos on ”ei löytynyt”.