İkili Arama Algoritması: İşlev, Yararlar, Zaman ve Mekan Karmaşıklığı

Tanıtım

Herhangi bir hesaplama sisteminde arama, geliştirilmesi gereken en kritik işlevlerden biridir. Arama teknikleri, dosya alma, indeksleme ve diğer birçok uygulamada kullanılır. Birçok arama tekniği mevcuttur. Bunlardan biri ikili arama tekniğidir.

Bir ikili arama algoritması , her yinelemede listenin yarısını ihmal etme fikri üzerinde çalışır. Belirli bir listede aradığı değeri bulana kadar listeyi bölmeye devam eder. İkili arama algoritması , basit bir doğrusal arama algoritmasına hızlı bir yükseltmedir .

Kodlama Deneyimi Gerektirmez. 360 ° Kariyer desteği. IIIT-B ve upGrad'dan Makine Öğrenimi ve Yapay Zeka alanında PG Diploması.

İkili Arama Algoritmasının Çalışması

Unutulmaması gereken ilk şey, ikili arama algoritmasının her zaman sıralı bir listede çalıştığıdır. Bu nedenle ilk mantıklı adım, sağlanan listeyi sıralamaktır. Sıralamadan sonra listenin ortancası istenilen değerle kontrol edilir.

• İstenen değer, merkezi indeksin değerine eşitse, indeks cevap olarak döndürülür.

• Hedef değer, listenin merkezi endeksin anlaşmasından düşükse, listenin sağ tarafı yok sayılır.

• İstenen değer, merkezi endeksin değerinden büyükse, sol yarı atılır.

• İşlem daha sonra hedef değer bulunana kadar kısa listelerde tekrarlanır.

Örnek 1

Algoritmayı bir örnekle inceleyelim. Aşağıdaki numaraları içeren bir liste olduğunu varsayalım:

1, 15, 23, 7, 6, 14, 8, 3, 27

İstenen değeri 27 olarak alalım. Listedeki toplam eleman sayısı 9'dur.

İlk adım, listeyi sıralamaktır. Sıralamadan sonra liste şöyle görünür:

1, 3, 6, 7, 8, 14, 15, 23, 27

Listedeki eleman sayısı dokuz olduğundan, merkezi indeks beş olacaktır. Beşinci indeksteki değer 8'dir. İstenen değer olan 27, 8 değeri ile karşılaştırılır. İlk önce, değerin 8'e eşit olup olmadığını kontrol edin. Evet ise, dizini döndürün ve çıkın.

27, 8'den büyük olduğundan, sol kısmı yok sayar ve yalnızca listenin sağ tarafını geçerdik. Geçiş yapılacak yeni liste:

14, 15, 23, 27

Not: Pratikte liste kesilmez. Sadece gözlem daraltılmıştır. Dolayısıyla “yeni liste”, yeni bir liste yapmak veya orijinalini kısaltmak olarak karıştırılmamalıdır. Yeni bir liste ile uygulanabilmesine rağmen, iki sorun var. İlk olarak, bir bellek yükü olacak. Her yeni liste, alan karmaşıklığını artıracaktır. İkincisi, orijinal dizinlerin her yinelemede izlenmesi gerekir.

Yeni merkezi indeks, uygulamaya bağlı olarak ikinci veya üçüncü unsur olarak alınabilir. Burada üçüncü unsuru merkezi olarak ele alacağız. 23 değeri 27 değeri ile karşılaştırılır. Değer merkezi değerden büyük olduğu için sol yarıyı atacağız.

Geçiş yapılacak liste şudur:

27

Liste yalnızca tek bir öğe içerdiğinden, merkezi öğe olarak kabul edilir. Bu nedenle, istenen değeri 27 ile karşılaştırırız. Eşleştikçe, orijinal listede 27'nin indeks değerini döndürürüz.

2. Örnek

Aynı listede istenen değeri 2 olarak kabul edelim.

İlk olarak, merkezi değer olan sekiz, 2 ile karşılaştırılır. İstenen değer merkezi değerden daha küçük olduğu için odağımızı listenin sol tarafına daraltırız.

Yeni geçiş şunlardan oluşacaktır:

1, 3, 6, 7

Merkez elemanı ikinci eleman olarak alalım. İstenen değer iki, 3 ile karşılaştırılır. Değer hala daha küçük olduğundan, odağı tekrar listenin sol tarafına daraltırız.

Yeni geçiş şunlardan oluşacaktır:

1

Çapraz liste yalnızca bir öğeye sahip olduğundan, değer doğrudan kalan öğeyle karşılaştırılır. Değerlerin eşleşmediğini görüyoruz. Bu nedenle, bir hata mesajıyla döngüden çıkarız: v alue not found .

Veri Bilimi Gelişmiş Sertifikasyonu, 250'den Fazla İş Ortağı, 300'den Fazla Eğitim Saati, %0 EMI

Zaman ve Mekan karmaşıklığı

İkili arama algoritmasının zaman karmaşıklığı O(log n)'dir. Merkezi indeks istenen değerle doğrudan eşleştiğinde en iyi durum zaman karmaşıklığı O(1) olacaktır. En kötü durum senaryosu, listenin her iki ucundaki değerler veya listede olmayan değerler olabilir.

İkili arama algoritmasının uzay karmaşıklığı, algoritmanın uygulanmasına bağlıdır. Bunu uygulamanın iki yolu vardır:

1. yinelemeli yöntem
2. özyinelemeli yöntem

Her iki yöntem de uygulamadaki iki farklılıkla tamamen aynıdır. İlk olarak, özyinelemeli yöntemde döngü yoktur. İkincisi, yeni değerleri döngünün bir sonraki yinelemesine geçirmek yerine, onları bir sonraki özyinelemeye geçirir. Yinelemeli yöntemde yinelemeler döngü koşulları aracılığıyla kontrol edilebilirken, özyinelemeli yöntemde sınır koşulu olarak maksimum ve minimum kullanılır.

Yinelemeli yöntemde, uzay karmaşıklığı O(1) olacaktır. Özyinelemeli yöntemde, uzay karmaşıklığı O(log n) olacaktır.

Faydalar

• İkili arama algoritması , uygulanması oldukça basit bir arama algoritmasıdır .

• Doğrusal aramaya göre önemli bir gelişmedir ve uygulanması daha zor olan bazı arama algoritmalarına kıyasla hemen hemen aynı performansı gösterir.

• İkili arama algoritması , listeyi sırayla taramak yerine her yinelemede listeyi ikiye böler. Büyük listelerde bu yöntem gerçekten yararlı olabilir.

Ödeme: Karar Ağacı Sınıflandırması: Bilmeniz Gereken Her Şey

Çözüm

İkili arama algoritması , hesaplama alanında yaygın olarak kullanılan bir algoritmadır . Hem büyük hem de küçük veri kümelerinde iyi çalışabilen, şişman ve doğru bir arama algoritmasıdır. İkili arama algoritması , uygulanması basit ve güvenilir bir algoritmadır. Zaman ve mekan analizi ile, bu özel tekniği kullanmanın faydaları açıktır.

Veri bilimi hakkında bilgi edinmek istiyorsanız, çalışan profesyoneller için oluşturulan ve 10'dan fazla vaka çalışması ve proje, uygulamalı uygulamalı atölye çalışmaları, endüstri uzmanlarıyla mentorluk sunan IIIT-B & upGrad'ın Veri Biliminde PG Diplomasına göz atın, 1- endüstri danışmanlarıyla bire bir, en iyi firmalarla 400+ saat öğrenim ve iş yardımı.