Tehtävä:
Toinen puolitushaku

Tätä tehtävää ei pidä yrittää ennen kuin olet tehnyt tehtävän Puolitushaku.

Oletamme, että T on kasvavassa suuruusjärjestyksessä. Kuten tehtävässä Puolitushaku todettiin, alla olevan algoritmin löytämä x:n esiintymä ei ole välttämättä ensimmäinen, mutta nyt emme katso sitä virheeksi. Kysymys kuuluu: toimiiko alla oleva algoritmi muuten oikein? Siis, onko varmaa että jos x esiintyy T:ssä, niin algoritmi palauttaa x:n jonkin esiintymän paikan; ja muutoin algoritmi palauttaa 0?

Perustele vastauksesi joko antamalla vastaesimerkki tai todistamalla algoritmi aina oikein toimivaksi.

Vastaesimerkki on sellaiset n, T ja x, että algoritmi palauttaa väärän vastauksen. Osoita vastaesimerkki päteväksi suorittamalla algoritmi niillä.

Todistuksen täytyy olla samankaltainen kuin tehtävässä Puolitushaku, mutta kovin suora kopio se ei voi olla, koska algoritmeissa on isoja eroja. Todista, että algoritmi pysähtyy ja että sen palauttama vastaus on oikein.

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