Logaritmikus keresés

Rendezett tömbben úgy keresünk, hogy az eljárás során kiszámítjuk az adott tömb középpontját, majd a keresett számról eldöntjük, hogy az ott talált érték alatt vagy felett helyezkedik el a keresett szám. Ezt a tömbszakaszt használjuk a következő felezéshez. Vagyis ha 20 elemű tömböt veszünk, a 10. elem értékét összehasonlítjuk a keresett értékkel. Ha az kisebb, mint a 10. elem, az 1-9-ig terjedő tömböt használjuk a következő felezésnél. Ha nagyobb a keresett érték, mint a 10. elem, akkor a 11-20-ig terjedő tömböt. A felezéseket addig ismételjük, amíg megtaláljuk a keresett értéket a tömbben, vagy összeért, vagy átfedésbe került a felezett sorozat alsó és felső határa. A ciklus lépésszáma nagyjából log N.

Legyen az adat.csv fájl tartalma az alábbi:

1,5,65,13,46,36,23,76,87,99,27,49,32,95,48,33,66,45,88,11

Rendezzük sorba, és írjuk ki az eredményt a sorted.csv-be. A rendezéshez használjuk a python beépített megoldását.

#!/user/bin/python
#felolvassuk az adat.csv fájl első sorát
fp = open("adat.csv")
s = fp.readline()
fp.close();
 
#tömbbe daraboljuk a karakterláncot a vesszők mentén
tomb = s.split(",")
#itt minden elemet számmá alakítunk, hogy a sorba rendezéskor számszerű növekvő sorozatot kapjunk
for i in range(len(tomb)):
    tomb[i]=int(tomb[i])
#sorba rendezzük a tömböt
tomb.sort()
#itt minden elemet szöveggé alakítunk, hogy összefűzhessük karakterlánccá
for i in range(len(tomb)):
    tomb[i]=str(tomb[i])
 
#kiírjuk a karakterláncba fűzött tömböt a sorted.csv fájlba
fp = open("sorted.csv","w+")
fp.write(",".join(tomb))
fp.close()

A keresés megvalósításakor ismét felolvassuk a sorted.csv fájlt. A kereséskor nem minden tömbelemet hasonlítunk össze a keresett értékkel. Ezért elegendő az összehasonlításban felhasznált tömbelemeket számmá alakítani.

#!/user/bin/python
fp = open("sorted.csv")
s = fp.readline()
fp.close();
tomb = s.split(",")
ah = 0
fh = len(tomb)-1
szam=int(args[1])
while 1:
  i=(ah+fh)/2
  if int(tomb[i])<szam:
       ah=i+1
  if int(tomb[i])>szam:
       fh=i-1
  if ah>=fh or int(tomb[i])==szam:
      break
if ah<=fh:
    print "sorszam:",i

A programot lefuttatva az alábbi eredményt kapjuk:

$ python logsearch.py 32
sorszam: 6

Ha a rendezett tömbben a keresett szám többször szerepel, bizonytalan hogy azok közül melyiket találja meg az algoritmus. Ezért ha az első indexét keressük, ki kell bővítenünk az algoritmust egy lineáris, vagy annál hatékonyabb kereséssel.