1  a := 1; y := n+1
2  while a < y do
3      v := ⌊(a+y)/2⌋
4      if T[v] < x then
5          a := v+1
6      else
7          y := v

Tehtävä:
Puolitushaku

Lyhyt MathCheck-ohje (uuteen välilehteen)

Puolitushaku on nopea keino löytää haluttu kohta kasvavassa järjestyksessä olevasta taulukosta. Sen perusajatus on seuraava (yksityiskohdissa esiintyy vaihtelua). Aluksi etsintäalueena on koko taulukko. Jos etsintäalueen puolivälissä oleva alkio on suurempi kuin etsittävä, etsintäalueen yläpuolikas hylätään ja etsintää jatketaan alapuolikkaasta samalla periaatteella. Jos etsintäalueen puolivälissä oleva alkio on pienempi kuin etsittävä, etsintää jatketaan yläpuolikkaasta.

Seuraavat merkinnät on hyvä osata.

muuttuja := lausekeLausekkeen arvo sijoitetaan muuttujaan.
while ehto do
    lauseita
Jos ehto pätee, suoritetaan lauseet ja palataan testaamaan ehtoa; muutoin lopetetaan.
if ehto then
    lauseita1 else
    lauseita2
Jos ehto pätee, suoritetaan lauseita1; muutoin suoritetaan lauseita2.
⌊…⌋Pyöristetään alaspäin lähimpään kokonaislukuun.
;Lopettaa lauseen (käytetään selvyyden vuoksi erottamaan samalla rivillä olevat lauseet toisistaan).

Tarkastelemme ensin seuraavaa yritystä toteuttaa puolitus­haku. Taulukkoa A indeksoidaan 1, …, n. Jos x:ää ei löydetä, palautetaan 0. Rivillä 3 on pyöristys alaspäin, jotta tulos olisi kokonais­luku ja sitä voisi käyttää taulukon indeksinä.

1  a := 1; y := n
2  while a < y do
3      v := ⌊(a+y)/2⌋
4      if T[v] = x then return v
5      if T[v] < x then a := v+1
6      else y := v−1
7  return 0

Testaamme algoritmia tapauksella n = 3, T = [6,7,8] ja x = 6. While-silmukan ensimmäisellä kierroksella v saa arvon , joten T[v] = . Riveistä 4, 5 ja 6 se, jonka loppuosa suoritetaan, on rivi .
tai

Sen jälkeen a = ja y = , joten algoritmi lopettaa ja palauttaa vastauksen . Algoritmin olisi pitänyt palauttaa .
tai

Tämä voitaisiin korjata vaihtamalla rivin 6 loppuosaksi y := v, mutta algoritmi toimisi silti yhä väärin kun x = 8. Kenties kaikki virheet korjaantuisivat vaihtamalla ≤ riville 2, mutta miten voimme varmistua asiasta?

Muutamme algoritmia toisella tavalla, koska nykyisellään siinä on vielä yksi huono piirre: jos x:n arvo esiintyy T:ssä useasti, algoritmi saattaa palauttaa ensimmäisen, viimeisen tai jonkin muun esiintymän paikan. Esimerkiksi kun n = 3 ja x = 6, algoritmi palauttaa taulukosta [5,6,6] ensimmäisen esiintymän paikan ja taulukosta [6,6,7] viimeisen esiintymän paikan. Jos halutaan löytää kaikki esiintymät, joudutaan taulukkoa selaamaan löydetystä esiintymästä alkaen molempiin suuntiin. Olisi parempi, että algoritmi palauttaisi aina ensim­mäisen esiintymän paikan, jotta riittäisi selata taulukkoa oikealle.

Siksi muutamme algoritmin tällaiseksi:

1  a := 1; y := n+1
2  while a < y do
3      v := ⌊(a+y)/2⌋
4      if T[v] < x then
5          a := v+1
6      else
7          y := v

Tavoitteemme on todistaa, että tämä algoritmi toimii oikein kaikilla syötteillä. Se on kopioitu oikealle alas.

Kun jatkossa kysytään arvoa verrattuna toiseen operaat­torilla <, ≤, ≥ tai >, vastaukseksi halutaan tiukin mahdollinen arvo, joka varmasti pätee annetuilla tiedoilla. Jos esim. pystytään päättelemään että x < 1, vastaus x < 5 ei kelpaa vaikka sekin on totta.

MathCheck saattaa antaa vastaesimerkiksi muuttujien arvo­yhdistelmän, joka ei voi esiintyä tutkittavassa algoritmissa. Se on silti osoitus siitä, että vastaus ei ollut oikein. Vasta­esimerkin lukuarvot ovat yleensä avuksi vastauksen korjaamiseksi, mutta eivät aina, koska jotkut tarkastukset suoritetaan modulaarisessa aritmetiikassa (koska MathCheck ei osaa parempaa) ja niistä saattaa tulla hulluja lukuja.

Ensin osoitamme, että algoritmi pysähtyy kaikilla syötteillä. Mitä rivin 3 alussa voidaan varmasti sanoa y:n arvosta a:n funktiona?
y ≥ tai

Mitä rivin 3 alussa voidaan varmasti sanoa lausekkeen (a+y)/2 arvosta? Valitse kaikki todet vaihtoehdot.
(a+y)/2 ≥ a
(a+y)/2 > a
(a+y)/2 ≥ y
(a+y)/2 > y
(a+y)/2 ≤ a
(a+y)/2 < a
(a+y)/2 ≤ y
(a+y)/2 < y
tai

Mitä rivin 4 alussa voidaan varmasti sanoa muuttujan v arvosta? Kirjoita myös operaattorit =, ≠, <, ≤, > ja/tai ≥ sen mukaan kuin tarvitaan.
tai

Tarkastellaan tapausta, jossa suoritus kulkee rivin 5 kautta. Tarkoittakoot a ja y muuttujien a ja y arvoja rivin 3 alussa. Tarkoittakoot A ja Y muuttujien a ja y arvoja rivin 5 lopussa. Rivin 5 suorittamisen vuoksi A = v+1, ja v:n arvoa pohdittiin äsken. Mitä voidaan sanoa A:sta a:n funktiona ja Y:stä y:n funktiona? Kirjoita myös =, ≠, <, ≤, > ja/tai ≥.
ja tai
Niinpä . tai

Jos rivin 3 jälkeen ei suoriteta riviä 5, niin suoritetaan rivi 7. Tarkoittakoot A ja Y muuttujien a ja y arvoja rivin 7 lopussa. Mitä voidaan sanoa A:sta a:n funktiona ja Y:stä y:n funktiona? Kirjoita myös =, ≠, <, ≤, > ja/tai ≥.
ja tai
Niinpä . tai

Saimme siis molemmissa tapauksissa tulokseksi, että while-silmukan vartalon suoritus pienentää kokonais­lukua y−a. Koska silmukan ehto on a < y ja se tarkoittaa samaa kuin , voidaan päätellä, että jos algoritmin alussa a = a0 ja y = y0, niin silmukan vartalo suoritetaan korkeintaan y0−a0 kertaa. Tämä takaa, että algoritmi pysähtyy kaikilla syötteillä. (Tarkempi analyysi osoittaisi, että algoritmin suoritus­aika on likimain verrannollinen lukuun log2(y0−a0).)
tai

Seuraavaksi tarvitsemme tiedon, että aina rivin 2 alussa pätee a ≤ y. Tyhjän taulukon tapauksessa n = 0 ja muutoin n > 0. Niinpä, kun riville 2 tullaan ensimmäisen kerran, a = ja y = .
tai

Olkoon symboleilla a, y, v, A ja Y sama merkitys kuin edellä. Jos suoritetaan rivi 7, pätee A = a ≤ v = Y, missä a ≤ v oli päätelty edellä ja muut tiedot voi helposti päätellä suoraan algoritmin koodista. Niinpä A ≤ Y. Kirjoita vastaava ketju, joka perustelee väitteen A ≤ Y siinä tapauksessa, että suoritetaan rivi 5.
tai

Olemme osoittaneet, että kun riville 2 tullaan uudelleen, a ≤ y pätee riippumatta siitä, kuljettiinko silmukan vartalossa rivin 5 vai rivin 7 kautta. Sitä ennen osoitimme, että a ≤ y pätee myös kun riville 2 tullaan ensimmäisen kerran. Siksi a ≤ y pätee aina rivin 2 alussa.

Algoritmi lopettaa silloin kun silmukan ehto ei toteudu. Tällöin voidaan päätellä edellistä voimakkaampi a:ta ja y:tä koskeva väite. Se on .
tai

Ei siis tarvitse miettiä, kummasta muuttujasta vastaus luetaan, koska niillä on sama arvo.

Jos riviä 5 ei koskaan suoriteta, niin algoritmin lopetettua a = . Jos rivi 5 suoritetaan ainakin kerran, niin algoritmin lopetettua T[] < x. Kummassakaan tapauksessa a ei ole liian pieni, eli ei voi olla niin, että x esiintyy taulukossa ennen kohtaa a.
tai

Jos riviä 7 ei koskaan suoriteta, niin algoritmin lopetettua y = . Jos rivi 7 suoritetaan ainakin kerran, niin algoritmin lopetettua T[] ≥ x. Kummassakaan tapauksessa y ei ole liian suuri, eli ei voi olla niin, että x:n ensimmäinen esiintymä taulukossa on kohdan y jälkeen.
tai

Koska a = y ja tämä kohta ei ole liian pieni eikä liian suuri, se on oikea. Se tarkoittaa, että jos x esiintyy taulukossa, niin a ja y sisältävät ensimmäisen esiintymän kohdan. Myös pätee että jos x ei esiinny taulukossa, niin a ja y sisältävät sen kohdan, johon x kuuluisi. Jos x on suurempi kuin mikään taulukon alkio, niin a ja y sisältävät arvon , mikä tarkoittaa, että x kuuluisi taulukon viimeisen alkion perään.
tai

Puolitushakualgoritmimme toimii siis juuri niin kuin pitääkin!