Lineáris keresés

Nézzük meg, mit csinált az előző két programozási tétel:

• Az eldöntés arra volt jó, hogy megnézzük, van-e adott tulajdonságú elem a sorozatban
• A kiválasztás esetében biztosak voltunk benne, hogy van adott tulajdonságú elem, és a tétel megmondta, hogy melyik ez az elem.

Nem csináltad meg a feladatokat?? Akkor neked zzzz!

A keresés ez a kettő együtt: megmondja, hogy melyik az adott tulajdonságú elem, ha van, ha meg nincs, akkor megmondja, hogy nincs.

Valójában már csináltunk is ilyet, méghozzá a 23h feladatban. Nézd csak meg a kiválasztásos posztot!

Mindenesetre itt van róla a videó:

A lineáris keresés programozási tétel pszeudokódja a következő:

sorozat = valamilyen lista, range, vagy más bejárható objektum

ciklus sorozat minden elem-ére
    ha az elem keresett tulajdonságú:
        egy változóba tesszük az indexét
        logikai változóban felírjuk magunknak, hogy találtunk ilyet
        break (azaz kilépünk a ciklusból)
    elágazás vége
ciklus vége

ha volt keresett tulajdonságú elem:
    kiírjuk az elemet, vagy az indexét
különben:
    kiírjuk, hogy nem volt ilyen elem
elágazás vége

Bár szó szerint lekódolható a fenti algoritmus Pythonban is, a tétel igazi Python-kódja kicsit másmilyen, mégpedig azért, mert a for utasítás else-záradéka annyira ritka csoda a proramozás nyelvek széles világában, hogy nem szokás gondolni rá. Te azért csak gondolj!

Átfogalmazzuk a pszeudokódot a for-else lehetőséget szem előtt tartva:

sorozat = valamilyen lista, range, vagy más bejárható objektum

ciklus sorozat minden elem-ére
    ha az elem keresett tulajdonságú:
        kiírjuk, vagy logikai változóban tároljuk az elemet vagy az indexét
        break (azaz kilépünk a ciklusból)
    elágazás vége
ciklus vége
ha rendesen végigfutott a ciklus (azaz nem volt break):
    kiiírjuk, hogy nem volt ilyen elem
elágazás vége

Na, akkor ez Pythonban, értékek szerint bejárva a listánkat:

for elem in bejárható_objektum:
    if elem olyan_amilyet_keresünk:
        print(elem)
        break
else:
    print('nem volt ilyen')

És indexek szerint bejárva a listánkat:

for index in range(len(bejárható_objektum)):
    if bejárható_objektum[index] olyan_amilyet_keresünk:
        print('Az elem helye:', index, 'maga az elem:', bejárható_objektum[index])
        break
else:
    print('nem volt ilyen')

A Python egyszerűsítése:

• Lényegében az előző két tétel egyszerűsítését nézzük, együtt. Az in operátorral meg tudjuk mondani, hogy van‑e keresett érték, a lista objektumtípus index() tagfüggvényével meg azt, hogy ez az érték hányadik.
• Megjegyezzük, hogy az index() csak az első előfordulás indexét adja meg, azaz csak egy előfordulást talál meg. Ha több is van – akkor így jártunk. Persze a tétel teljes formája sem jobb.
• És az egyszerűsítés szokás szerint csak olyan esetben használható, amikor konkrét értéket keresünk. Azaz megtaláljuk vele az első 1241-et a megtanulandó évszámok listájában, de nem találjuk meg az első olyan számot, ami nagyobb 1000-nél. (Illetve deeee, de majd csak ha már lényegesen okosabbak vagyunk:))
• És akkor, ennyi pofázás után:

  if elem in bejárható_objektum:
      print('Van', elem, 'itt:', bejárható_objektum.index(elem))
  else:
      print('Nincs', elem)
  

De miért “lineáris” keresés?

Részint “csak”, de valójában azért, mert a végrehajtásához szükséges idő lineárisan (egyenesen) arányos a bejárható objektum elemszámával. Hogy akkor van másmilyen keresés is? Fogadhatsz rá. Nagyon ráérünk megtanulni.

Feladatok

F0024a: Vágd be a lineáris keresés tételét! (Megoldás itt :P)

F0024b: Kódold le a pszeudokód első változatát!

F0024c: Adott az 5, 4, 3, 4, 5, 4, 4, 5, 3, 1 sorozat. Van-e benne egymás mellett két azonos szám? Ha igen, hol? (Megoldás itt.)

F0024d: Adott a ['Sanyi', 'Manyi', 'Jani', 'Pali', 'Olga', 'Pali', 'Pista'] lista. Van-e benne két egyforma név (nem csak egymás mellett, hanem bárhol)? (Megoldás itt.)
(Ha már végeztél, akkor elolvashatod – igen, fehérrel van írva, kijelölöd, és látszik – : Megtanultad a videóból, hogy mennyire jó, ha átgondolod, hogy pontosan mi a francot kérdeznek? Hogy megfogalmazható-e egyszerűbben a kérdés?)

F0024e: Adott a 3, 6, 4, 9, 8, 11, 12, 20 sorozat. Van-e benne két olyan szomszédos szám, amelyek csak 1-gyel térnek el egymástól? (Barátod az abs.) (Megoldás itt.)

Az előző alkalommal kiválasztottunk. Legközelebb megszámolunk.

(A méh: http://www.azkillerbeessoftball.com/uploads/8/5/0/6/8506277/4778556.jpg)