Doğrusal Arama Algoritmasına Giriş: Giriş ve Özellikler[Örneklerle]

Arama Nedir?

Arama, bir öğe listesinde belirli bir öğeyi bulma işlemidir. Belirli bir kaydın aranmasına yardımcı olur. Bu nedenle, belirli bir öğenin yerini belirleme tekniğidir. Bir arama sürecinin başarısı, aranacak öğenin tanımlanıp tanımlanmamasına bağlıdır.

Veri yapısı, verilerin iki yöntemle aranmasını sağlar.

1. Doğrusal arama veya sıralı arama
2. Ikili arama

Doğrusal Arama

Doğrusal arama algoritmaları, verilerin sıralı olarak aranması için kullanılan bir algoritma türüdür. Bu algoritma, O(n) karmaşıklığına sahip belirli bir elemanı bulur. Bir öğe koleksiyonuna uygulanır. Verilerin her bir öğesi sırayla aranır ve aranan öğeyle eşleşirse döndürülür. Hiçbir eşleşme bulunamazsa, arama toplanan verilerin sonuna kadar devam eder. Temelde listede gezinirken her öğeyi keşfetme tekniğidir. Arama algoritması hem sıralanmış hem de sıralanmamış verilere uygulanabilir. Pratik olarak doğrusal arama, ikili arama algoritmaları ve karma tablolar gibi diğer arama algoritmaları tarafından sağlanan daha hızlı arama seçenekleri nedeniyle nadiren kullanılır.

Doğrusal arama algoritmasındaki adımlar

• Arama öğesinin kullanıcı tarafından okunması.
• Aranacak eleman, listenin ilk elemanı ile sıkıştırılır.
• Öğeler eşleşirse, bir dönüş oluşturulur.
• Elemanlar eşleşmezse, aranacak eleman listenin ikinci elemanı ile karşılaştırılır.
• Öğe eşleşene kadar işlem tekrarlanır.

Doğrusal arama algoritmalarının özellikleri

1. Genellikle sıralanmamış veya sıralanmamış verilerin küçük bir listesine uygulanır.
2. Zaman doğrusal olarak eleman sayısına bağlıdır, bu nedenle O(n) ise zaman karmaşıklığına sahiptir.
3. Uygulaması çok basittir.

Doğrusal arama algoritmaları

Öğe bulunmadıkça ve bulunana kadar sürekli bir döngü yöntemi devam eder.

• algoritma Seqnl_Search(liste, öğe)
• Ön: liste != ;
• Gönderi: bulunursa öğenin dizinini döndürür, aksi takdirde: 1
• dizin <- fi
• while indeksi < list.Cnt ve liste[index] != item //cnt: sayaç değişkeni
• dizin <- dizin + 1
• biterken
• if index < list.Cnt ve list[index] = item
• dönüş endeksi
• eğer son
• dönüş: 1
• Seqnl_Search'ü sonlandır

Doğrusal arama örneği

Problem: n elemanlı bir arr[] dizisi verildiğinde, arr[] içinde verilen bir x elemanını aramak için bir fonksiyon yazın.

Şekil 1: Doğrusal arama algoritmasının uygulanmasını gösteren bir kod örneği

Kaynak

Doğrusal arama algoritmaları birçok programlama dilinde kullanılabilir.

1. Python'da doğrusal arama

Şekil 2: Python dilinde doğrusal bir arama algoritmasını gösteren bir kod örneği

Kaynak

Çıktı: Öğe dizin 3'te mevcut

2. C'de doğrusal arama

Şekil 3: C dilinde doğrusal bir arama algoritmasını gösteren bir kod örneği

Kaynak

Çıktı : Öğe dizin 3'te mevcut

3. Veri yapısında doğrusal arama

Veri yapısında doğrusal bir arama problemi için sözde kod

Şekil 4: Doğrusal arama algoritması için sözde kod

Kaynak

Ikili arama

İkili arama, bir dizi öğedeki öğeleri aramak için bir algoritmadır. Doğrusal arama algoritmasıyla karşılaştırıldığında, ikili arama algoritması sıralanmış bir veri listesine uygulanır.

İkili arama algoritması aşağıdaki adımları içerir

• Aranacak elemanın liste veya dizinin ortasından eleman ile karşılaştırılması.
• Öğe, listedeki öğeyle eşleşirse, ortadaki öğenin dizinini döndürür.
• Eğer eşleşme dönmezse elemanın ortadaki elemandan büyük veya küçük olup olmadığına bakılır.
• Ortadaki elemandan daha büyük değere sahip bir eleman için arama dizinin sağ tarafında yapılır.
• Benzer şekilde, öğenin değeri ortadaki öğeden daha küçükse, arama listenin sol tarafına yapılır.

Bu nedenle, ikili arama en iyi, veriler sıralanmış bir şekilde çok sayıda çubuk elemanı içerdiğinde uygulanır. Bu, arama algoritması için listenin/dizinin sıralanmasını zorunlu kılar.

İkili Aramanın Özellikleri

• İkili arama algoritması, bir dizideki çok sayıda öğeyi aramak için kullanışlıdır.
• İkili arama algoritması, O(logn) zaman karmaşıklığına sahiptir.
• İkili arama algoritmasının uygulanması basittir.

İkili Arama Algoritması

• Algoritma Binary_Search(liste, öğe)
• L'yi 0'a ve R'yi n'ye ayarlayın: 1
• L > R ise, Binary_Search başarısız olarak sonlandırılır
• Başka
• m'yi (orta elemandaki konum) (L + R) / 2 tabanına ayarlayın
• Am < T ise, L'yi m + 1 olarak ayarlayın ve 3. adıma gidin
• Am > T ise, R'yi m: 1 olarak ayarlayın ve 3. adıma gidin
• Şimdi, Am = T,
• arama yapılır; dönüş (m)

Çözüm

Bu yazımızda, Lineer Arama Algoritmasının ne olduğunu inceledik ve ayrıca Lineer Arama Algoritması kullanarak bir listeden belirli bir elemanın nasıl aranacağını detaylı olarak inceledik. Son olarak, Python 3'ü dil olarak kullanarak Doğrusal Arama Algoritmasını nasıl pratik olarak uygulayabileceğimizi ve istediğimiz çıktıyı nasıl elde edebileceğimizi de gördük.

Veri Bilimi ile ilgileniyorsanız, IIIT-B ve upGrad'ın çalışan profesyoneller için özenle hazırlanmış ve çok sayıda vaka çalışması, uygulamalı atölye çalışması, 1'e 1 mentorluk sunan Veri Biliminde Yönetici PG Programına göz atmalısınız. daha fazla.