Jump to content
  • entries
    16
  • comments
    0
  • views
    36,990

İkili arama (Binary Search)


Doğuhan ELMA

207 views

İkili arama (Binary Search), sıralanmış bir dizi veya liste üzerindeki bir öğeyi aramak için kullanılan bir arama algoritmasıdır. İkili arama, doğru veri setinde çok etkilidir çünkü her adımda arama alanını yarıya indirir. Bu da onu büyük veri setlerinde çok hızlı ve etkili kılar.

İkili aramanın temel prensipleri aşağıdaki gibidir:

Orta noktadaki öğeyi kontrol edin: Arama alanınızın orta noktasındaki öğeyi kontrol edin. Bu, arama alanınızın ilk ve son indeksinin ortalamasını alarak bulunabilir.

Arama alanını güncelleyin: Eğer orta noktadaki öğe aradığınız öğeye eşitse, işlem tamamlanır. Eğer aradığınız öğe orta noktadaki öğeden daha büyükse, arama alanınızı orta noktanın bir sağındaki öğeden son indekse kadar güncellersiniz. Eğer aradığınız öğe orta noktadaki öğeden daha küçükse, arama alanınızı ilk indeksten orta noktanın bir solundaki öğeye kadar güncellersiniz.

Adımları tekrar edin: Arama alanınızı her seferinde yarıya indirerek bu adımları tekrar edin.

binary-search-small.gif

Aşağıda, bir Python ikili arama işlemi örneği bulunmaktadır:

def binary_search(item_list, item):
    first = 0
    last = len(item_list) - 1
    found = False

    while (first<=last and not found):
        mid = (first + last) // 2
        if item_list[mid] == item:
            found = True
        else:
            if item_list[mid] < item:
                first = mid + 1
            else:
                last = mid - 1
    return found

print(binary_search([1, 2, 3, 5, 8], 6))   # Output: False
print(binary_search([1, 2, 3, 5, 8], 5))   # Output: True

Bu örnekte, ikili arama işlemi sıralanmış bir liste üzerinde gerçekleştirilir. Algoritma, önce listenin ortasını kontrol eder. Eğer aranan öğe bulunursa, algoritma True döndürür. Eğer aranan öğe ortadaki öğeden büyükse, algoritma ilk yarısını göz ardı eder ve ikinci yarıda arama yapar. Eğer aranan öğe ortadaki öğeden küçükse, algoritma ikinci yarısını göz ardı eder ve ilk yarıda arama yapar. Bu işlem, aranan öğe bulunana veya arama alanı kalmayana kadar devam eder.

İkili arama işlemini rekürsif olarak gerçekleştiren bir Python örneği bulabilirsiniz:

def binary_search_recursive(item_list, item, start, end):
    if start > end:
        return False

    mid = (start + end) // 2
    if item_list[mid] == item:
        return True
    elif item_list[mid] > item:
        return binary_search_recursive(item_list, item, start, mid-1)
    else: # item_list[mid] < item
        return binary_search_recursive(item_list, item, mid+1, end)


print(binary_search_recursive([1, 2, 3, 5, 8], 6, 0, 4))   # Output: False
print(binary_search_recursive([1, 2, 3, 5, 8], 5, 0, 4))   # Output: True

Bu örnekte, binary_search_recursive fonksiyonu, sıralanmış bir liste üzerindeki bir öğeyi arar. Fonksiyon, önce listenin ortasını kontrol eder. Eğer aranan öğe bulunursa, True döndürülür. Eğer aranan öğe ortadaki öğeden daha küçükse, fonksiyon kendisini ortadaki indeksin bir altı ve başlangıç indeksi ile tekrar çağırır. Eğer aranan öğe ortadaki öğeden daha büyükse, fonksiyon kendisini ortadaki indeksin bir üstü ve bitiş indeksi ile tekrar çağırır. Bu süreç, aranan öğe bulunana veya arama alanı kalmayana kadar devam eder. Bu tür bir sürece "rekürsiyon" denir.

1.pngSıralı Dizide 22 sayısının İkili Arama algoritmasıyla bulunması örneğidir.

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...