İkili Arama Tekniği

İkili Arama, sıralı bir dizide, belirli değerin bulunmasına yönelik bir algoritmadır. Bu teknikteki her bir adımda, aranan değerin, dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit olmaması durumunda aranan değerin orta değer tarafından ikiye ayrılan kısımlardan hangisinde olduğu kontrol edilir, aranan değeri içeren kısım bir sonraki adımda arama yapılacak dizi olur ve bu sayede arama yapılan listedeki eleman sayısı her adımda yarıya indirilmiş olur.

Bu algoritma ile N elemanlı bir dizide en fazla log_2 N karşılaştırma yaparak aranan değerin yerini bulmak mümkündür.

#!/usr/bin/python
# -*- coding: cp1254 -*-
"""
İkili arama, sıralı bir dizide, belirli değerin bulunmasına yönelik bir algoritmadır.
Dönen değer : Bulunursa , dizinin kaçıncı indizi olduğu
                    Bulunmazsa, -1
"""
def ikiliArama(aranan,dizi):
    bas = 0
    son = len(dizi)-1
    while ( bas != son ):
        i = int(round((bas + son )/2.0))
        if dizi[i] == aranan:
            return i
        elif dizi[i] > aranan:
            son = i
        else :
            bas = i
        if int(round((bas + son )/2.0)) == son:
            return -1

>>> dizi = [1,2,6,5,43,65,45,43,23,21,12,11,14,43,23,77,22,11,1,1,2]
>>> dizi.sort()
>>> print dizi
[1, 1, 1, 2, 2, 5, 6, 11, 11, 12, 14, 21, 22, 23, 23, 43, 43, 43, 45, 65, 77]
>>> ikiliArama(43,dizi)
15
>>> ikiliArama(44,dizi)
-1

(0) Yorum yaz! Baglanti

<<Önceki Sayfa |/|Sonraki Sayfa>>

@