Doğrusal arama mantığı
- Algoritmalar kursu
- Başlangıç
- Ders 13/80
- 4 dk
Bir diziyi baştan sona gezerek hedefi aramanın O(n) algoritması olduğunu öğrenirsin.
Doğrusal arama mantığı
Doğrusal arama, bir dizide hedef elemanı bulmak için en basit yöntemdir: baştan sona her elemanı sırayla kontrol eder.
Eleman hedefe eşitse indeksi döndürülür. Dizinin sonuna gelinirse ve hedef bulunmamışsa -1 döndürülür.
Karmaşıklık analizi
Doğrusal aramanın en kötü durumu O(n)'dir: hedef son elemandaysa tüm dizi gezilir. En iyi durum O(1)'dir: hedef ilk elemandaysa.
Ortalama durum da O(n)'dir çünkü hedef ortalama olarak dizinin ortasındadır ve yarışı gezilir.
Uygulama Doğrusal arama
linear_search(arr, target) yaz. Hedefi bul, indeksi döndür; bulunamazsa -1. print(linear_search([4, 2, 7, 1], 7)) ile 2 yazdır.
Başlangıç kodu
def linear_search(arr, target):
# Hedefi araÖrnek çözüm
def linear_search(arr, target):
# Hedefi ara
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
print(linear_search([4, 2, 7, 1], 7))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Doğrusal aramanın en kötü durumu nedir?
- O(1) Doğru cevap
- O(log n)
- O(n)
- O(n^2)
Açıklama: En kötü durum O(n)'dir.
2 Bulunamadı değeri
Hedef bulunamazsa ____ döndürülür.Hedef bulunamazsa -1 döndürülür.Açıklama: -1 doğru.
3 Doğrusal arama mantığı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Doğrusal arama |
Sırayla kontrol |
O(n) |
En kötü durum |
O(1) |
En iyi durum |
-1 |
Bulunamadı |