Doğrusal Arama: Python, C++ Örnek E-posta
Arama Algoritması Nedir?
Bir arama algoritması, belirli bir veri yapısına sahip bir öğe veya nesne koleksiyonundan bir öğe veya nesne bulmak için tasarlanmıştır. Örneğin, belirli bir yükseklik listesinden minimum yüksekliği arayın veya bir sayı listesinden veya dizisinden en yüksek puanı arayın. Birkaç popüler arama algoritması arasında "Doğrusal Arama", "İkili Arama", "Atlamalı Arama", "Fibonacci Arama" vb. bulunur.
Doğrusal Arama Nedir?
Doğrusal arama en basit arama algoritmalarından biridir. Belirli bir liste veya diziden, verilen öğeyi tek tek arar. Doğrusal Arama, tüm listeyi yineler ve belirli bir öğenin arama öğesine eşit olup olmadığını kontrol eder. Aynı zamanda 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 öğenin 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?
Tamsayı sayıları içeren bir dizi diyelim. Görev, dizide belirli bir sayıyı 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'i başlat
) 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 (Öge i nolu indekste bulunduğu için). 8. adıma gidin.
) 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ıralı Arama Algoritması için Sahte Kod
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 negative index is not valid return -1
C++ Kod Örneği Doğrusal Arama
#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(arr[0]); int item; cout << "Enter a number to search: "; cin >> item; int idx = linearSearch(arr, 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 Kod Örneği Doğrusal Arama
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
Genellikle, zaman karmaşıklığı, belirli bir görevi gerçekleştirmek için gereken CPU zamanı miktarı anlamına gelir. Doğrusal arama algoritmasında görev, dizinin öğesinden 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. Arama öğesini 0 ila n-1 indeksi arasında bulabiliriz. En kötü senaryoda, algoritma dizideki tüm öğeleri arama öğesiyle eşleştirmeye çalışacaktır.
Bu durumda en kötü durum karmaşıklığı O(n) olacaktır. Burada, “O”-büyük O Notasyonu karmaşıklık fonksiyonunu ifade eder.
En İyi Durum Senaryosunda Doğrusal Aramanın Zaman Karmaşıklığı:
Diyelim ki dizide ilk konumda bulunan bir öğeyi arıyoruz. Bu senaryoda, doğrusal arama algoritması dizideki tüm n öğeyi aramayacaktır. Bu nedenle karmaşıklık O(1) olacaktır. Bu 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 uzay karmaşıklığı
Doğrusal arama için uzay karmaşıklığı her zaman O(N)'dir çünkü doğrusal arama fonksiyonunda herhangi bir geçici değişkeni depolamaya veya kullanmaya ihtiyacımız yoktur.
Doğrusal Arama Algoritması nasıl geliştirilir?
Arama, programın yaşam döngüsü boyunca birden fazla kez yapılabilir. Ayrıca doğrusal arama algoritmasını çalıştırıyor ve belirli bir anahtarı birkaç kez arıyor olmamız da mümkündür. “İ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 öğesiyle 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 Verileri [5] ve verileri[4] değiştirin. Daha sonra veri dizisi şöyle görünecektir:
Veri [] = {1,5,9,8,4,7,3,11}
Şimdi dikkat ederseniz bir anahtar ne kadar sık aranıyorsa indeksi de o kadar azalıyor. Böylece karşılaştırma sayısı azalıyor.
Öne doğru hareket edin:
Bu yöntemde 0. indeksteki arama elemanını değiştiriyoruz. Çünkü tekrar aranırsa O(1) zamanında bulabiliriz.
Doğrusal Arama Algoritmasının Uygulanması
İşte kullanabileceğimiz bazı doğrusal arama uygulamaları.
- Küçük boyutlu diziler veya listedeki yalnızca birkaç öğe için doğrusal aramayı 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.