Doğrusal ve İkili Arama Algoritmaları Açıklaması

Bazı verileri arama yeteneği, bilgisayar biliminin önemli bir yönüdür. Arama algoritmaları, bir veri kümesindeki belirli bir öğeyi aramak için kullanılır.

Algoritmalar, bir arama sorgusuna bir boole sonucu (doğru veya yanlış) döndürür. Bulunan değerin göreli konumunu vermek için de değiştirilebilirler.

Bu makale için algoritmalar, bir değerin var olup olmadığını belirlemeye odaklanacaktır.

Doğrusal Arama Algoritmaları

Doğrusal arama, sıralı arama olarak da bilinir. Bu arama türünde, bir listedeki her bir değer, istenilen değerin var olup olmadığı kontrol edilirken sıralı bir şekilde tek tek ziyaret edilir.

Algoritma, aradığınız değeri bulana veya aranacak değerler bitene kadar değeri değere göre kontrol eder. Aranacak değerler bittiğinde, bu, arama sorgunuzun listede olmadığı anlamına gelir.

Sıralı bir arama algoritması, bir değerler listesi ve listedeki istenen öğeyi parametreleri olarak alır. Dönüş sonucu şu şekilde başlatılır: Yanlış ve değişecek NS İstenen değer bulunduğunda.

Örnek olarak aşağıdaki Python uygulamasına bakın:

def linearSearch (listem, öğe):

bulundu = Yanlış

indeks = 0

while index < len (mylist) ve bulunamadı:

mylist[index] == item ise:

bulunan = Doğru

Başka:

dizin = dizin+1

dönüş bulundu

Algoritma Analizi

En iyi durum senaryosu, istenen öğe listedeki ilk öğe olduğunda ortaya çıkar. En kötü durum, istenen öğe listenin sonuncusu (n. öğe) olduğunda ortaya çıkar. Bu nedenle, doğrusal arama için zaman karmaşıklığı O(n)'dir.

Yukarıdaki algoritmadaki ortalama durum senaryosu n/2'dir.

İlişkili: Big-O Notasyonu Nedir?

Değiştirilmiş Doğrusal Arama

Kullanılan algoritmanın, kendisine rastgele bir öğe listesi sağlandığını varsaydığını bilmek önemlidir. Yani, liste öğeleri belirli bir sırada değildir.

Öğelerin belirli bir sırada olduğunu varsayalım, örneğin küçükten büyüğe. Hesaplamada bazı avantajlar elde etmek mümkün olacaktır.

Verilen listede 19 aramaya bir örnek alın: [2, 5, 6, 11, 15, 18, 23, 27, 34]. 23'e ulaştıktan sonra, aranan öğenin listede olmadığı anlaşılacaktı. Bu nedenle, liste öğelerinin geri kalanını aramaya devam etmek artık önemli olmayacaktır.

İkili Arama Algoritmaları

Sıralı bir listenin gerekli hesaplamayı nasıl azaltabileceğini gördünüz. İkili arama algoritması, sıralı bir listeye sahip olmanın getirdiği bu verimlilikten daha da fazla yararlanır.

Algoritma, sıralı bir listenin orta değerini alarak ve bunun istenen değer olup olmadığını kontrol ederek başlar. Değilse, istenen değerden küçük veya büyük olup olmadığına bakılır.

Daha azsa, listenin alt yarısını kontrol etmeye gerek yoktur. Aksi takdirde, daha büyükse, listenin üst yarısına geçer.

İlişkili: Özyineleme Nedir ve Nasıl Kullanılır?

Hangi alt liste (sol veya sağ) seçilirse seçilsin, yine ortadaki değer belirlenecektir. Değer, gerekli değer olup olmadığı tekrar kontrol edilir. Değilse, istenen değerden küçük veya büyük olup olmadığına bakılır.

Bu işlem, eğer oradaysa bir değer bulunana kadar tekrarlanır.

Aşağıdaki Python uygulaması ikili arama algoritması içindir.

def ikiliSearch (listem, öğe):

düşük = 0

yüksek = uzun (benim listem) - 1

bulundu = Yanlış

iken düşük <= yüksek ve bulunamadı:

orta = (düşük + yüksek) // 2

eğer listem[mid] == öğe:

bulunan = Doğru

elif item < listem[orta]:

yüksek = orta - 1

Başka:

düşük = orta + 1

dönüş bulundu

Algoritma Analizi

En iyi durum senaryosu, istenen öğenin ortadaki öğe olduğu tespit edildiğinde ortaya çıkar. Yine de en kötü durum senaryosu o kadar basit değil. Aşağıdaki analizi izleyin:

İlk karşılaştırmadan sonra n/2 öğe bırakılacaktır. Saniyeden sonra n/4 öğe kalacak. Üçüncüden sonra, n/8.

i'nin karşılaştırma sayısı olduğu n/2i'ye ulaşana kadar öğe sayısının yarıya inmeye devam ettiğine dikkat edin. Tüm bölmelerden sonra, sadece 1 öğe ile sonuçlanırız.

Bu şu anlama gelir:

n/2i=1

Bu nedenle, ikili arama O(log n)'dir.

Sıralamaya Geçmek

İkili aramada, verilen dizinin zaten sipariş edildiği bir durumu düşündük. Ancak, sıralanmamış bir veri kümeniz olduğunu ve üzerinde ikili arama yapmak istediğinizi varsayalım. Sen ne yapardın?

Cevap basit: sıralayın. Bilgisayar biliminde iyi araştırılmış bir dizi sıralama tekniği vardır. Çalışmaya başlayabileceğiniz bu tekniklerden biri, seçim sıralama algoritmasıdır, diğer alanlarla ilgili birçok kılavuzumuz da vardır.

Seçim Sıralaması Nasıl Kullanılır

Seçim sıralaması, yeni başlayanlar için anlaşılması biraz zor, ancak bir şeylerin hızını aldığınızda çok zor değil.

Sonrakini Oku

Yazar hakkında