C Programlama #28 | Dizide Arama: Doğrusal ve İkili Arama

Eğitmen: Dr. Süleyman Burak ÇELİK

Sözlükte bir kelimeyi ilk sayfadan başlayıp aramayız; ortadan açarız. Yirmi sekizinci derste bir dizide bir değeri bulmanın iki yolunu, doğrusal ve ikili aramayı, adım adım karşılaştırıyoruz. On öğrencinin okul numaraları sırasız bir dizide duruyor. Doğrusal arama baştan başlayıp her elemanı aranan değerle karşılaştırıyor: 1121 yedinci karşılaştırmada, indis 6'da bulunuyor; dizide olmayan 1050 için on elemanın hepsine bakılıyor ve fonksiyon -1 döndürüyor (hiçbir dizi indisi eksi olamaz). Dizideki bir değer ortalama olarak dizinin yarısında bulunur: karşılaştırmalar 1'den 10'a, toplam 55, ortalama 55 / 10 = 5.5. İkili arama sıralı bir dizi ister: arama aralığını ilk ve son değişkenleri tutuyor, orta = (ilk + son) / 2. 1121 için (0 + 9) / 2 = 4, d[4] = 1098, aranan daha büyük, ilk = 5; (5 + 9) / 2 = 7, d[7] = 1153, aranan daha küçük, son = 6; (5 + 6) / 2 = 5, d[5] = 1121: üç karşılaştırmada indis 5. 1050 için orta 4, 1, 2 ve 3'ten sonra ilk 3, son 2 oluyor; aralık boş, -1. Döngünün koşulundaki eşittir de önemli: ilk küçük eşit son yerine ilk küçüktür son yazılırsa, tek aday kaldığında döngü ona bakmadan biter ve program dizide olan 1076'yı bulamaz. İkili arama her karşılaştırmada kalan adayların yarısını eler: 1000 elemanda 1000, 500, 250, 125, 62, 31, 15, 7, 3 ve 1, yani en çok 10 karşılaştırma; bir milyon elemanda 20, bir milyarda 30. Programımız bunu her olası aranan değeri deneyerek doğruluyor (10 eleman için 4, 1000 için 10, bir milyon için 20). Son olarak ikili aramayı sırasız diziye uyguluyoruz: fonksiyon dizinin sıralı olduğunu varsayıp yanlış yarıyı eliyor ve dizide olan 1121'i bulamıyor; kabarcık sıralamasından sonra aynı arama indis 5'i veriyor. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Doğrusal arama: sırasız dizide baştan sona; -1 = bulunamadı; ortalama 5.5 karşılaştırma 2. İkili arama: orta = (ilk + son) / 2 ile adım adım 1121 ve 1050 3. Döngü koşulunda eşittir neden önemli: ilk küçüktür son hatası 4. Her karşılaştırma yarıyı eler: 1000 → 10, 1 milyon → 20 5. Sırasız dizide ikili arama yanlış sonuç verir Bölümler: 0:00 Dizide arama 0:19 Sözlükte bir kelime 0:46 Doğrusal arama 1:41 İkili arama 2:34 Aranan dizide yoksa 3:25 Her karşılaştırma yarıyı eler 4:07 Sırasız dizide ikili arama 4:48 Bugünün dört kuralı 5:12 Sonraki ders: iki boyutlu diziler Kaynak kitap: Paul Deitel, Harvey Deitel — C How to Program, 9. baskı (2022), §6.10. Konu sırası ve kavramlar kaynak kitaptan izlenir; anlatım, örnekler ve ekranlar özgündür. Hedef kitle: C'ye yeni başlayan tüm mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: C Programlama #01–#27.

Bu videoyu izlemek için Premium üyelik gerekir.