- Doğrusal Arama'yı kendi kelimelerinizle tanımlayın ve açıklayın
- Doğrusal arama gibi temel terimleri doğru kullanın
- Öğrendiklerinizi yeni örnek ve sorulara uygulayın
- Bu konuda öğrencilerin yaptığı yaygın hatalardan kaçının
Tüm çözümler eşit değildir: bazıları bir milyonluk listede bir ismi yirmi adımda bulur, bazıları ise bir milyona ihtiyaç duyar. GCSE seviyesinde, çalışan herhangi bir çözümü yazmaktan iyi çözümler yazmaya geçersiniz. Bu bölüm, klasik arama ve sıralama algoritmalarını ve hangisinin en iyi olduğunu nasıl ölçeceğinizi kapsar.
Bu ders, Doğrusal Arama'ya odaklanır: her öğeyi tek tek kontrol ederek öğeleri bulun.
Her öğeyi tek tek kontrol ederek öğeleri bulun.
Temel fikirler
İkili arama sıralı veri gerektirir
İkili arama, doğrusal aramadan çok daha hızlıdır — bir milyon öğe için yaklaşık 20 karşılaştırma — ama yalnızca liste önce sıralanmışsa çalışır. Sıralamanın da bir maliyeti vardır, bu yüzden sıralanmamış veride tek seferlik bir arama için doğrusal arama yine de kazanabilir. Doğru algoritma duruma bağlıdır, sadece teoriye değil.
En kötü durum önemlidir
Bir algoritma şanslı olup hedefi ilk denemede bulabilir, ama mühendisler en kötü duruma göre plan yapar — olabilecek en yavaş çalışmaya. Big-O bu büyümeyi açıklar: O(n), girdiyi iki katına çıkarmak süreyi kabaca iki katına çıkarır demektir; O(n²) ise girdiyi iki katına çıkarmak süreyi kabaca dört katına çıkarır demektir.
Terim — doğrusal arama: Hedef bulunana kadar listedeki her öğeyi tek tek kontrol etme. Basit, sıralanmamış listelerde çalışır ama büyük listelerde yavaştır.
[1, 3, 5, 7, 9, 11, 13] sıralı listesinde 7'yi bulmak için ikili arama kullanın.
low = 0, high = 6. Orta indis = (0 + 6) // 2 = 3. 3. indisteki öğe 5'tir. 5, 7'den küçüktür, bu yüzden sol yarıyı atın: low 4 olur. Orta indis = (4 + 6) // 2 = 5. 5. indisteki öğe 11'dir. 11, 7'den büyüktür, bu yüzden sağ yarıyı atın: high 4 olur. Orta indis = (4 + 4) // 2 = 4. 4. indisteki öğe 7'dir. Bulundu — 7, 4. indiste, sadece 3 karşılaştırmadan sonra.
Cevap: İkili arama 7'yi 4. indiste 3 karşılaştırmada bulur; doğrusal arama 4 karşılaştırmaya ihtiyaç duyardı.
- Sıralanmamış listede ikili arama kullanma Düzeltme: listeyi önce sıralayın ya da doğrusal arama kullanın — sıralanmamış veride ikili arama sadece yavaş değil, yanlış sonuç verir.
- Liste indislerinin 0'dan başladığını unutma Düzeltme: 7 öğelik bir listede son indis 6'dır — bir eksik/bir fazla hataları klasik sınav tuzağıdır, bu yüzden dikkatle izleyin.
Alıştırma
50 — hedef son sıradaysa ya da yoksa her öğe kontrol edilmelidir.
Yaklaşık 20 — her adım kalan öğeleri yarıya indirir, böylece bir milyon yaklaşık 20 yarıya indirmede bire iner.
Liste sıralanmamışsa ikili aramanın önce sıralanması gerekir — bu sıralama maliyeti, tek seferlik bir aramada daha hızlı aramayı dengeleyebilir.
O(n²) — girdi iki katına çıkınca dört katına çıkmak, ikinci dereceden büyümenin işaretidir.
Kısa kontrol
Aşağıdakilerden hangisi "doğrusal arama"yı en iyi tanımlar?
Doğru mu yanlış mı: ikili arama her zaman en iyi arama algoritmasıdır.
[5, 3, 8, 1] listesinde kabarcık sıralamanın bir geçişini izleyin. Liste sonrasında nasıl olur?
- Doğrusal Arama: her öğeyi tek tek kontrol ederek öğeleri bulun.
- İkili arama sıralı veri gerektirir: İkili arama doğrusal aramadan çok daha hızlıdır — bir milyon öğe için yaklaşık 20 karşılaştırma — ama yalnızca liste önce sıralanmışsa çalışır.
- İkili arama: Sıralı bir listeyi yarıya indirerek hedefi bulma — ortadaki öğeyle karşılaştırıp hedefi içeremeyecek yarıyı atma.
- Dikkat edin: sıralanmamış listede ikili arama kullanma