Doğrusal Arama: Python, C++ Örnek E-posta

Arama Algoritması Nedir?

Arama algoritması, belirli bir veri yapısına sahip bir öğe veya nesne koleksiyonundan bir öğeyi veya nesneyi bulmak için tasarlanmıştır. Örneğin, verilen bir yükseklik listesinden en düşük yüksekliği aramak veya bir sayı listesinden veya dizisinden en yüksek notu aramak gibi. Popüler arama algoritmalarından bazıları şunlardır: "Doğrusal Arama", "İkili Arama", "Sıçrama Arama", "Fibonacci Arama" vb.

Doğrusal Arama Nedir?

Doğrusal Arama Doğrusal arama, en basit arama algoritmalarından biridir. Verilen bir liste veya diziden, verilen elemanı tek tek arar. Doğrusal arama, tüm listeyi tarar ve belirli bir elemanın aranan elemana eşit olup olmadığını kontrol eder. Buna ayrıca doğrusal arama da denir. sıralı arama.

Doğrusal Arama Fonksiyonu ne işe yarar?

Bir tamsayı dizisi şu şekilde verilir:Numbers,” ve bir “öğe” değişkeni aranacak tam sayıyı içerir.

Şimdi, Doğrusal Arama algoritması aşağıdaki çıktıyı sağlayabilir:

• “-1”; bu, verilen elemanın dizide bulunmadığı anlamına gelir.
• 0 ile n-1 arasında herhangi bir sayı; aranan öğenin bulunduğu anlamına gelir ve dizideki öğenin dizinini döndürür. Burada “n” dizinin boyutunu temsil etmektedir.

Doğrusal Arama nasıl çalışır?

Diyelim ki, tamsayılar içeren bir dizimiz var. Görevimiz, verilen sayıyı bu dizide bulmaktır.

• Eğer sayı dizide yer alıyorsa o sayının indeksini döndürmemiz gerekiyor.
• Verilen sayı bulunamazsa -1 değerini döndürür.

Akış şemasında “Veri” tamsayı dizisini, “N” dizinin boyutunu, “öğe” ise dizide aramak istediğimiz sayıdır.

Doğrusal Arama Algoritmasının Akış Şeması:

Akış şemasının adımları şunlardır:

) 1 Adım Arama öğesini okuyun, "öğe."

) 2 Adım i=0 ve index=-1 değerlerini başlatın.

) 3 Adım Eğer ben

) 4 Adım Veri[i] "öğe"ye eşitse 5. adıma gidin. Aksi takdirde 6. adıma gidin.

) 5 Adım İndeks = i (Öğe i numaralı indekste bulunduğu için). 8. adıma geçin.

) 6 Adım ben = ben +1.

) 7 Adım 3. adıma gidin.

) 8 Adım Durdurun.

Basit olması açısından, bir tamsayı dizisi içeren bir örnek sunuyoruz. Doğrusal arama aynı zamanda dizede, nesneler dizisinde veya yapıda da uygulanabilir.

Sözde Code Sıralı Arama Algoritması için

Aşağıdaki sözde kod, yukarıda açıklanan doğrusal aramanın mantığını yakalamaktadır. Diziyi ilk indeksten başlayarak tarar ve eşleşme durumunda konumu döndürür, aksi takdirde -1 döndürür.

function linearSearch: in → Data[], item
    foundAt = -1
    for i in (0 to data.length):
        if data[i] equals item:
            // item is found in the array
            // returning the index
            return i
    // item not found in the array
    // -1 means no item found, as a negative index is not valid
    return -1

C++ Code Örnek Doğrusal Arama

İşte tam bir C++ Ardışık arama işlemini gerçekleştiren ve aranan değerin indeksini yazdıran program.

#include <bits/stdc++.h>
using namespace std;

int linearSearch(int *arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}

int main() {
    int array[] = {1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10};
    int n = sizeof(array) / sizeof(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

Çıktı:

Enter a number to search: -10
-10 is found at index 14

Python Code Örnek Doğrusal Arama

Aynı mantık burada da geçerlidir. Python Liste indeksleri üzerinde tek bir döngü kullanır ve eşleşen öğenin konumunu döndürür.

def linearSearch(data, item):
    for i in range(len(data)):
        if data[i] == item:
            return i
    return -1

data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else:
    print("{} was not found".format(item))

Çıktı:

Enter a number to search: -10
-10 is found at index 14

Doğrusal Arama Algoritmasının Karmaşıklık Analizi

Genel olarak, zaman karmaşıklığı, belirli bir görevi gerçekleştirmek için gereken CPU süresi anlamına gelir. Doğrusal arama algoritmasında, görev dizinin elemanları arasından arama anahtarını bulmaktır.

Üç tip zaman karmaşıklığı vardır:

• En kötü durum senaryosu
• En iyi durum senaryosu
• Ortalama Vaka Senaryosu

En Kötü Durum Senaryosunda Doğrusal Aramanın Zaman Karmaşıklığı:

Diyelim ki "n" boyutunda bir dizide doğrusal arama yapmamız gerekiyor. Aranacak öğeyi 0 ile n-1 indeksleri arasında bulabiliriz. En kötü senaryoda, algoritma dizideki tüm elemanları aranacak öğeyle eşleştirmeye çalışacaktır.

Bu durumda, en kötü durum karmaşıklığı O(n) olacaktır. Burada "O" - büyük O Gösterimi - karmaşıklık fonksiyonunu ifade eder.

En İyi Durum Senaryosunda Doğrusal Aramanın Zaman Karmaşıklığı:

Diyelim ki dizinin ilk konumunda bulunan bir elemanı arıyoruz. Bu senaryoda, doğrusal arama algoritması dizideki tüm n elemanı aramayacaktır. Dolayısıyla karmaşıklık O(1) olacaktır. Bu da sabit zaman anlamına gelir.

Ortalama durum senaryosunda doğrusal aramanın Zaman Karmaşıklığı:

Dizinin orta indeksinde bir eleman bulunduğunda, doğrusal arama için ortalama durum karmaşıklığının O(N) olduğu söylenebilir; burada N, dizinin uzunluğu anlamına gelir.

Doğrusal arama algoritmasının alan karmaşıklığı:

Doğrusal aramanın alan karmaşıklığı her zaman O(N)'dir çünkü doğrusal arama fonksiyonunda herhangi bir geçici değişkeni saklamamız veya kullanmamız gerekmez.

Doğrusal Arama Algoritması nasıl geliştirilir?

Programın yaşam döngüsü boyunca arama işlemi birden fazla kez yapılabilir. Ayrıca doğrusal arama algoritmasını çalıştırıp belirli bir anahtarı birkaç kez arıyor olabiliriz. Bunun için "İkili Arama Algoritması” dizi sıralanmış bir dizi ise.

Dizinin 10 bin sayıdan oluştuğunu ve hedef elemanın 5000. indekste bulunduğunu varsayalım. Böylece algoritma 5000 öğeyi karşılaştırmaya çalışacaktır. Artık karşılaştırmalar CPU ağırlıklı görevlerdir. Doğrusal arama algoritmasını optimize etmek için iki seçeneğimiz var.

• aktarma
• Öne Taşı

Aktarım:

Bu yöntemde, arama öğesini dizideki önceki öğeyle değiştireceğiz. Örneğin, aşağıdaki gibi bir diziniz olduğunu varsayalım:

Veri[] = {1,5,9,8,7,3,4,11}

Şimdi Aktarımın 4. Adımlarını aramak istiyoruz:

) 1 Adım “4” indeks 6'da bulunur. Altı karşılaştırma yapıldı.

) 2 Adım Verileri[6] ve verileri[5] değiştirin. Daha sonra veri dizisi şöyle görünecektir:

Veri[] = {1,5,9,8,7,4,3,11}

) 3 Adım 4'ü tekrar arayın. Dizin 5'te bulundu. Bu sefer beş karşılaştırma yapıldı.

) 4 Adım data[5] ve data[4]'ü yer değiştirin. O zaman veri dizisi şöyle görünecektir:

Veri[] = {1,5,9,8,4,7,3,11}

Şimdi fark ettiyseniz, bir anahtar ne kadar sık ​​aranırsa, indeks o kadar azalır. Dolayısıyla, karşılaştırma sayısı da azalır.

Öne doğru hareket edin:

Bu yöntemde, arama elemanını 0. indekse taşıyoruz. Çünkü tekrar arandığında, onu O(1) sürede bulabiliyoruz.

Doğrusal Arama Algoritmasının Uygulanması

İşte kullanabileceğimiz bazı doğrusal arama uygulamaları.

• Küçük boyutlu diziler veya listede yalnızca birkaç eleman bulunduğunda, doğrusal arama kullanmak daha kolaydır.
• Doğrusal arama yöntemi tek veya çok boyutlu diziler veya diğer veri yapıları.
• Genel olarak doğrusal arama, "sırasız" verilerde arama yapmak için basit ve etkilidir. Verilen sırasız listeden tek bir veriyi kolaylıkla getirebiliriz.

SSS