İkili aramayı öğrenmeden önce şunu öğrenelim:
Arama nedir?
Arama, kullanıcısının bir veritabanında tutulan belgeleri, dosyaları, medyayı veya diğer türden verileri bulmasını sağlayan bir yardımcı programdır. Arama, kriterleri kayıtlarla eşleştirme ve kullanıcıya gösterme basit prensibiyle çalışır. Bu şekilde en temel arama işlevi çalışır.
İkili Arama nedir?
İkili arama, sıralı bir öğe listesinden veri bulup getiren gelişmiş bir arama algoritması türüdür. Temel çalışma prensibi, istenen değer bulunana ve arama sonucunda kullanıcıya gösterilinceye kadar listedeki verileri ikiye bölmeyi içerir. İkili arama, genellikle yarım aralıklı arama veya logaritmik arama olarak bilinir .
Bu algoritma eğitiminde şunları öğreneceksiniz:
- Arama nedir?
- İkili Arama nedir?
- İkili Arama Nasıl Çalışır?
- Örnek İkili Arama
- Neden İkili Aramaya İhtiyacımız Var?
İkili Arama Nasıl Çalışır?
İkili arama şu şekilde çalışır:
- Arama işlemi, sıralı veri dizisinin orta elemanının yerini belirleyerek başlar.
- Bundan sonra, anahtar değeri, öğeyle karşılaştırılır
- Anahtar değeri ortadaki öğeden küçükse aramalar, karşılaştırma ve eşleştirme için orta öğeye kadar üst değerleri analiz eder
- Anahtar değerinin ortadaki öğeden daha büyük olması durumunda aramalar, karşılaştırma ve eşleştirme için orta öğeye kadar düşük değerleri analiz eder.
Örnek İkili Arama
Bir sözlük örneğine bakalım. Belirli bir kelimeyi bulmanız gerekiyorsa, hiç kimse her kelimeye sıralı bir şekilde geçmez, ancak gerekli kelimeyi aramak için en yakın kelimeleri rastgele bulur.
Yukarıdaki görüntü şunları göstermektedir:
- 10 basamaklı bir diziniz var ve 59 öğesinin bulunması gerekiyor.
- Tüm elemanlar 0 - 9 arası indeks ile işaretlenir. Şimdi dizinin ortası hesaplanır. Bunu yapmak için, dizinin en sol ve en sağ değerlerini alır ve bunları 2'ye bölersiniz. Sonuç 4.5'tir, ancak biz taban değerini alıyoruz. Dolayısıyla orta 4'tür.
- Algoritma, 59'un 24'ten büyük olması nedeniyle ortadaki (4) tüm öğeleri en düşük sınıra düşürür ve artık dizide yalnızca 5 öğe kalmıştır.
- Şimdi, 59, 45'ten büyük ve 63'ten küçüktür. Ortadaki 7'dir. Dolayısıyla, sağdaki indeks değeri, 6'ya eşit olan orta - 1 olur ve sol indeks değeri, 5 olan öncekiyle aynı kalır.
- Bu noktada, 59'un 45'ten sonra geldiğini biliyorsunuz. Dolayısıyla 5 olan sol indeks de orta olur.
- Bu yinelemeler, dizi yalnızca bir öğeye indirgenene veya bulunacak öğe dizinin ortası haline gelene kadar devam eder.
Örnek 2
İkili aramanın çalışmasını anlamak için aşağıdaki örneğe bakalım
- 2 ile 20 arasında değişen sıralı değerler diziniz var ve 18'i bulmanız gerekiyor.
- Alt ve üst sınırların ortalaması (l + r) / 2 = 4'tür. Aranan değer, 4 olan orta değerden daha büyüktür.
- Ortadan küçük dizi değerleri aramadan çıkarılır ve orta değer 4'ten büyük değerler aranır.
- Bu, aranacak asıl öğe bulunana kadar tekrar eden bir bölme işlemidir.
Neden İkili Aramaya İhtiyacımız Var?
Aşağıdaki nedenler, ikili aramayı bir arama algoritması olarak kullanmak için daha iyi bir seçim haline getirir:
- İkili arama, verilerin boyutu ne olursa olsun sıralanmış veriler üzerinde verimli bir şekilde çalışır
- Verileri bir sırayla gözden geçirerek aramayı gerçekleştirmek yerine, ikili algoritma gerekli öğeyi bulmak için verilere rastgele erişir. Bu, arama döngülerini daha kısa ve daha doğru hale getirir.
- İkili arama, daha yavaş ve çoğunlukla yanlış olan eşitlik karşılaştırmalarını kullanmak yerine bir sıralama ilkesine dayalı olarak sıralanmış verilerin karşılaştırmalarını gerçekleştirir.
- Her arama döngüsünden sonra, algoritma dizinin boyutunu ikiye böler, dolayısıyla bir sonraki yinelemede dizinin yalnızca kalan yarısında çalışacaktır.
Özet
- Arama, kullanıcısının belgeleri, dosyaları ve diğer veri türlerini aramasını sağlayan bir yardımcı programdır. İkili arama, sıralı bir öğe listesinden veri bulup getiren gelişmiş bir arama algoritması türüdür.
- İkili arama, genellikle yarım aralıklı arama veya logaritmik arama olarak bilinir
- Gerekli eleman bulunan her yinelemede diziyi ikiye bölerek çalışır.
- İkili algoritma, sol ve en sağdaki dizin değerlerinin toplamını 2'ye bölerek dizinin ortasını alır. Şimdi, algoritma, bulunacak öğeye bağlı olarak, dizinin ortasından öğelerin alt veya üst sınırını düşürür. .
- Algoritma, gerekli öğeyi bulmak için verilere rastgele erişir. Bu, arama döngülerini daha kısa ve daha doğru hale getirir.
- İkili arama, sıralı verilerin karşılaştırmalarını yavaş ve yanlış olan eşitlik karşılaştırmalarını kullanmak yerine bir sıralama ilkesine göre gerçekleştirir.
- İkili arama, sıralanmamış veriler için uygun değildir.