Otsing (iti0140)

Allikas: Lambda

Realiseerida etteantud mooduli peale kaks otsingu algoritmi: jada- ja kahendotsing. gimme_my_input funktsioonist saab kätte tuple, kus esimene element on list ja teine listi genereerimiseks kasutatud juhuslike numbrite generaator. Kasutades generaatorit uute numbrite võtmiseks, sooritada listi pikkus korda otsinguid saadud listist. Kõigepealt tehes seda jadaotsinguga, siis kahendotsinguga.

Kahendotsingu sooritamiseks tuleks list enne ära sortida mõne pythoni sisseehitatud sortimisega. Jadaotsing ja kahendotsing realiseerida ise, jadaotsingu puhul teha ka tsükkel ise. Kahendotsingu lahendamiseks tuletage meelde, kuidas mängida arvu arvamise mängu.

0. Ma mõtlen numbrist 0-100 vahel (nt 72).

1. Kas on 50-st suurem? Jah -> 50-100 vahel.

2. Kas on 75-st suurem? Ei -> 50-75 vahel.

3. Kas on 62-st suurem? Jah -> 62-75 vahel.

4. Kas on 68-st suurem? Jah -> 68-75 vahel.

5. Kas on 71-st suurem? Jah -> 71-75 vahel.

6. Kas on 73-st suurem? Ei -> 71-73 vahel.

7. Kas on 72? Jah


Otsingu sooritamisel ei tohiks teha uusi liste. Kasutage olemaolevat listi ja ülemise ning alumise raja indeksit.

Otsingufunktsioonide definitsioonideks võiks kasutada järgnevat. Teha eraldi funktsioonid sisendi saamiseks ja otsingute väljakutsumiseks.

   def linear_search(lst, num):
   """
   Return True if found, False otherwise.
   """
   pass
   def binary_search(lst, num):
   """
   Return True if found, False otherwise.
   """
   pass