Python - Algoritmaları Arama

Verileri farklı veri yapılarında sakladığınızda arama çok temel bir gerekliliktir. En basit değerlendirme, veri yapısındaki her bir elemanın üzerinden geçmek ve aradığınız değerle eşleştirmektir. Bu, Doğrusal arama olarak bilinir. Verimsizdir ve nadiren kullanılır, ancak bunun için bir program oluşturmak, bazı gelişmiş arama algoritmalarını nasıl uygulayabileceğimiz hakkında bir fikir verir.

Doğrusal Arama

Bu tür aramada, tüm öğeler üzerinde tek tek sıralı arama yapılır. Her öğe kontrol edilir ve bir eşleşme bulunursa o belirli öğe döndürülür, aksi takdirde arama veri yapısının sonuna kadar devam eder.

def linear_search(values, search_for):
    search_at = 0
    search_res = False

# Match the value with each data element	
    while search_at < len(values) and search_res is False:
        if values[search_at] == search_for:
            search_res = True
        else:
            search_at = search_at + 1

    return search_res

l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))

Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -

True
False

İnterpolasyon Araması

Bu arama algoritması, gerekli değerin problama konumu üzerinde çalışır. Bu algoritmanın düzgün çalışması için, veri toplama sıralı bir biçimde ve eşit olarak dağıtılmış olmalıdır. Başlangıçta araştırma konumu, koleksiyonun en ortasındaki öğenin konumudur, bir eşleşme olursa öğenin dizini döndürülür. Ortadaki öğe öğeden daha büyükse, araştırma konumu orta öğenin sağındaki alt dizide yeniden hesaplanır. Aksi takdirde, öğe, ortadaki öğenin solundaki alt dizide aranır. Bu işlem, alt dizinin boyutu sıfıra düşene kadar alt dizide de devam eder.

Aşağıdaki programda belirtilen orta konumu hesaplamak için özel bir formül vardır.

def intpolsearch(values,x ):
    idx0 = 0
    idxn = (len(values) - 1)

    while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:

# Find the mid point
	mid = idx0 +\
               int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
                    * ( x - values[idx0])))

# Compare the value at mid point with search value 
        if values[mid] == x:
            return "Found "+str(x)+" at index "+str(mid)

        if values[mid] < x:
            idx0 = mid + 1
    return "Searched element not in the list"


l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))

Yukarıdaki kod çalıştırıldığında, aşağıdaki sonucu verir -

Found 2 at index 0