previous next Up Title Contents Index

4.4.2 Puolitushaku

Mikäli 13 korttiasi on järjestyksessä ja sinun pitäisi mahdollisimman vähällä pläräämisellä löytää vaikkapa pata 4, niin miten voisit menetellä? 
	1. laita pakka pöydälle kuvapuolet ylöspäin
	2. laita pakka puoliksi
	3. laita molemmat pakat pöydälle kuvapuolet ylöspäin
	4. kummassako kasassa etsittävä on?
	5. heitä se pakka pois jossa etsittävä ei ole
	6. jos etsittävä ei päällimmäinen, niin jatka kohdasta 1.
Vaikuttaa tyhmältä 13 kortille, mutta kokeilepa 1000 kortilla! Tai kokeile nyt etsiä ÄYSTÖÄ puhelinluettelosta tällä algoritmilla.

Tehtävä 4.16 Puolitushaku

Kirjoita puolitushausta kunnon "lausekielinen versio" kun meillä on sivunumeroitu kirja, jonka kullakin sivulla on täsmälleen yhden henkilön tiedot. Sivunumeroita kirjassa on N- kappaletta. Aloitat sivuista S1=0 ja S2=N+1. Miten jatkat mikäli pitää etsiä nimi NIMI?

Tehtävä 4.17 Puolitushaun kompleksisuus

Mikä on puolitushaun kompleksisuus?

previous next Up Title Contents Index