Doğrusal Arama ve İkili Arama: Doğrusal Arama ve İkili Arama Arasındaki Fark

Yayınlanan: 2021-02-09

İçindekiler

Tanıtım

Programlama dillerinde bitişik bellek tahsisi, birden çok veri noktasının depolanması için esnek bir uygulama sağlar. Verileri ayırmak ve tüm benzer verileri bir dizi, liste vb. gibi bitişik bir veri yapısında birleştirmek istiyorsak, bu en üst düzeyde kullanılabilir.

Bitişik bellek tahsisi, bilgisayarlardaki bir işletim sistemi, veri tabanı yönetim sistemleri vb. gibi gerçek dünya uygulamalarında birçok uygulamaya sahiptir. Bu veri yapısı esnek bir yapı olarak kabul edilir, çünkü bir diziye yeni bir veri noktası eklemek sadece tek bir zaman birimi gerektirir; O(1).

Ancak sorun, belirli bir girişe bakmak veya belirli bir girişi aramak istediğimizde ortaya çıkar, çünkü tüm gerçek dünya uygulamaları veri erişim komutlarına dayanır. Ve bu görev, işlemcinin ve belleğin hızını karşılayacak kadar hızlı olmalıdır.

Öğeyi aramak için yaptığımız karşılaştırma sayısına göre bölünmüş çeşitli arama algoritmaları vardır.

Bir öğeyi aramak için dizideki her veri noktasını karşılaştırırsak, sıralı bir arama olarak kabul edilir. Ancak bazı karşılaştırmaları atlayarak yalnızca birkaç öğeyi karşılaştırıyorsak, bu bir aralık araması olarak kabul edilir. Ancak, üzerinde bir aralık araması yapmak için sıralı düzende (artan düzende veya azalan düzende) bir diziye ihtiyacımız var.

Sıralı aramanın zaman karmaşıklığı doğrusal O(n)'dir ve ikili aramanın zaman karmaşıklığı (aralıklı aramanın bir örneği) O(log n)'dir. Ayrıca, üstel arama, atlamalı arama vb. gibi başka arama algoritmaları da vardır.

Ancak doğrusal arama ve ikili arama çoğunlukla, doğrusal aramanın rastgele veya sıralanmamış veriler için olduğu ve ikili aramanın sıralanmış ve sıralanmış veriler için olduğu yerlerde kullanılır. Hashing, bir veri noktasına erişmenin zaman karmaşıklığının O(1) olduğu özel bir arama algoritmasıdır.

Önce doğrusal arama ve ikili arama algoritmalarını gözden geçirelim ve ardından doğrusal arama ile ikili arama arasındaki farkları karşılaştıralım.

Doğrusal Arama

Daha önce tartışıldığı gibi, doğrusal arama algoritması dizideki her öğeyi karşılaştırır ve işte bunu yapmak için kod.

genel sınıf UpGrad {
genel statik int lineer_search ( int [] dizi, int n, int k){
for ( int i= 0 ; i<n; i++)
if (dizi[i]==k)
dönüş i+ 1 ;
dönüş – 1 ;
}
public static void main (String[] args){
int [] dizi= yeni int []{ 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
int k= 13 ;
int n=dizi.uzunluk;
int r=doğrusal_arama(dizi, n, k);
if (r==- 1 )
System.out.println( "eleman bulunamadı" );
Başka
System.out.println( “ +r+ ” konumunda eleman bulundu” );
}
}

Kodu inceleyelim.

Parametre olarak bir dizi, tamsayı anahtarı bekleyen bir linear_search işlevi bildirdik. Şimdi tüm elemanlar üzerinde döngüye girmeli ve arama anahtarımızla eşleşip eşleşmediğini karşılaştırmamız gerekiyor, bu yüzden dizi üzerinde döngü yapan bir for döngüsü yazdık ve içinde, o konumdaki sayının eşleşip eşleşmediğini kontrol eden bir if döngüsü var. arama tuşu ile veya değil. Bir eşleşme bulursak pozisyona geri döneceğiz. Dizide böyle bir öğe yoksa, işlevin sonunda -1 değerini döndürürüz.

Aynı sayının birden çok görünümü varsa, ilk oluşum konumunu döndüreceğimize dikkat edin.

Ana yönteme gelince, bir tamsayı dizisi bildirdik ve başlattık. Ardından aranması gereken anahtarı başlatıyoruz. Burada diziyi ve anahtarı sabit kodluyoruz, ancak bunu kullanıcı girişi olarak değiştirebilirsiniz. Artık elementlerin listesi ve aranacak anahtar elimizde olduğuna göre, lineer arama metodu çağrılır ve döndürülen indeks not edilir. Daha sonra, döndürülen değeri kontrol ediyoruz ve anahtar varsa dizini yazdırıyoruz, aksi takdirde yazdırma anahtarı bulunamadı.

Ikili arama

İkili arama, doğrusal aramaya göre daha optimize edilmiştir, ancak ikili aramayı uygulamak için dizinin sıralanması gerekir. Ve işte bunu yapmak için kod.

genel sınıf UpGrad {
genel statik int ikili_arama ( int [] dizi, int k){
int l= 0 ,h=dizi.uzunluk- 1 ,orta= 0 ;
while (l<=h){
orta=l+(hl)/ 2 ;
if (dizi[mid]==k)
orta + 1'e dönüş ;
else if (dizi[mid]>k)
h=orta- 1 ;
Başka
l=orta+ 1 ;
}
dönüş – 1 ;
}
public static void main (String[] args){
int [] dizi= yeni int []{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
int k= 8 ;
int r=binary_search(dizi,k);
if (r==- 1 )
System.out.println( "eleman bulunamadı" );
Başka
System.out.println( “ +r+ ” konumunda eleman bulundu” );
}
}

Kodu inceleyelim.

Parametre olarak sıralanmış bir tamsayı dizisi ve bir tamsayı anahtarı bekleyen bir binary_search yöntemi bildirdik. Low, high, mid değişkenlerini başlatıyoruz. Burada düşük, yüksek, düşükün 0 dizininde olacağı ve yüksekin başlangıçta n dizininde olacağı işaretçilerdir. Peki ikili arama nasıl çalışır?

İlk başta, düşük ve yüksek ortasını hesaplayacağız. Ortayı (düşük+yüksek)/2 olarak hesaplayabiliriz, ancak bazen yüksek büyük bir sayı olabilir ve yüksekten düşük eklemek tamsayı taşmasına neden olabilir. Yani ortayı düşük+(yüksek-düşük)/2 olarak hesaplamak en uygun yol olacaktır.

Ortadaki öğeyi arama tuşuyla karşılaştıracağız ve bir eşleşme bulursak dizini döndüreceğiz. Aksi takdirde, orta elemanın anahtardan büyük mü yoksa anahtardan mı küçük olduğunu kontrol edeceğiz. Orta daha büyükse, dizinin ikinci yarısındaki tüm öğeler anahtardan daha büyük olduğundan dizinin yalnızca ilk yarısını kontrol etmemiz gerekir, bu nedenle yüksek olanı orta 1'e güncelleyeceğiz.

Benzer şekilde, orta anahtardan küçükse, dizinin ikinci yarısında arama yapmamız gerekir, bu nedenle düşük olanı orta + 1'e günceller. Her yinelemede dizinin yarısından birini yok saydığımız için ikili aramanın azaltma ve fethetme algoritmasına dayandığını unutmayın.

Kodumuza geri dönersek, ana yöntemi oluşturduk. Sıralanmış bir dizi ve arama anahtarı başlattı, ikili aramaya bir çağrı yaptı ve sonuçları yazdırdı.

Artık hem doğrusal arama hem de ikili arama algoritmalarını inceledik ve şimdi her iki algoritmayı da karşılaştıralım.

Doğrusal Arama ve İkili Arama

Çalışma

Doğrusal arama, tüm öğeleri yineler ve bunları aranması gereken anahtarla karşılaştırır.
İkili arama, aranması gereken dizinin boyutunu akıllıca azaltır ve anahtarı her seferinde orta öğeyle karşılaştırır.

Veri yapısı

Doğrusal arama, dizi, liste, bağlantılı liste vb. tüm veri yapılarıyla esnektir.
Çok yönlü geçişe ihtiyacımız olduğundan, tüm veri yapılarında ikili arama yapılamaz. Dolayısıyla tek bağlantılı liste gibi veri yapıları kullanılamaz.

Önkoşullar

Her tür veri üzerinde doğrusal arama yapılabilir, veriler rastgele veya sıralı olabilir, algoritma aynı kalır. Bu nedenle herhangi bir ön çalışma yapılmasına gerek yoktur.
İkili arama yalnızca sıralanmış bir dizide çalışır. Dolayısıyla bir diziyi sıralamak bu algoritma için bir ön koşuldur.

Kullanım Örneği

Doğrusal arama genellikle daha küçük ve rastgele sıralı veri kümeleri için tercih edilir.
Nispeten daha büyük ve sıralanmış veri kümeleri için ikili arama tercih edilir.

Verimlilik

Doğrusal arama, daha büyük veri kümelerinde daha az verimlidir.
Daha büyük veri kümelerinde ikili arama daha verimlidir.

Zaman Karmaşıklığı

Doğrusal aramada, en iyi durum karmaşıklığı, öğenin ilk dizinde bulunduğu O(1)'dir. En kötü durum karmaşıklığı, öğenin son dizinde bulunduğu veya dizide bulunmadığı O(n)'dir.
İkili aramada, öğenin orta dizinde bulunduğu en iyi durum karmaşıklığı O(1)'dir. En kötü durum karmaşıklığı O( log 2 n).

kuru çalışma

10.000 boyutlu bir dizimiz olduğunu varsayalım.

Doğrusal bir aramada, en iyi durum karmaşıklığı O(1) ve en kötü durum karmaşıklığı O(10000)'dir.
İkili aramada, en iyi durum karmaşıklığı O(1) ve en kötü durum karmaşıklığı O( log 2 10000)=O(13.287)'dir.

Çözüm

Dizilerde veri erişiminin önemini anladık, doğrusal arama ve ikili aramanın algoritmalarını anladık. Doğrusal arama ve ikili arama kodlarını inceledim. Doğrusal arama ve ikili arama arasındaki farklar karşılaştırıldığında, büyük boyutlu bir örnek için kuru bir çalışma yapılmıştır.

Artık doğrusal arama ve ikili arama arasındaki farkların farkında olduğunuza göre, büyük bir kümelenmiş veri kümesi için her iki kodu da çalıştırmayı deneyin ve yürütme süresini karşılaştırın, farklı arama algoritmalarını keşfetmeye başlayın ve bunları uygulamayı deneyin!

Veri bilimi hakkında bilgi edinmek istiyorsanız, IIIT-B & upGrad'ın ç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 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ı.

Dünyanın en iyi Üniversitelerinden çevrimiçi veri bilimi kurslarını öğrenin . Kariyerinizi hızlandırmak için Yönetici PG Programları, Gelişmiş Sertifika Programları veya Yüksek Lisans Programları kazanın.

Karmaşıklıklarını kullanarak doğrusal arama ve ikili aramayı karşılaştırın.

İkili Arama, özellikle öğeler sıralanmış durumdayken, birçok yönden Doğrusal Arama'dan daha optimize edilmiş ve verimlidir. Sebep, her iki aramanın karmaşıklığına kadar kaynar.
Doğrusal Arama
1. Zaman Karmaşıklığı: O(N) - Doğrusal aramada olduğundan, herhangi bir öğenin anahtarla eşleşip eşleşmediğini kontrol etmek için dizi boyunca hareket ederiz. En kötü senaryoda, eleman dizinin sonunda olacak, bu yüzden sondan geçmemiz gerekecek ve bu nedenle zaman karmaşıklığı O(N) olacak, burada N, dizi elemanlarının toplam sayısıdır.
2. Uzay Karmaşıklığı: O(1) - Fazladan boşluk kullanmıyoruz, dolayısıyla uzay karmaşıklığı O(1) olacak.
Ikili arama
1. Zaman Karmaşıklığı: O(log N) - İkili Aramada, dizinin ortasına bakmamız gerektiğinden arama yarıya iner. Ve aramamızı sürekli olarak elementin bulunduğu bölümün ortasına kadar kısaltıyoruz.
2. Uzay Karmaşıklığı: O(1)
- Fazladan boşluk kullanmıyoruz, bu nedenle alan karmaşıklığı O(1) olacaktır.

Dizideki bir öğeyi aramak için başka bir yöntem var mı?

Arama için genellikle doğrusal arama ve ikili arama kullanılsa da, gerçekten de başka bir arama yöntemi vardır - enterpolasyon yöntemi. Tüm öğelerin eşit olarak dağıtıldığı Binary Search'ün optimize edilmiş bir sürümüdür.
Bu yöntemin arkasındaki fikir, ikili aramada her zaman dizinin ortasına bakmamızdır. Ancak bu yöntemde arama, anahtarın bulunduğu yere göre farklı yerlere gidebilir. Örneğin, anahtar dizinin son elemanına yakınsa, arama dizinin sonundan başlar.

Enterpolasyon aramasının farklı zaman karmaşıklıkları nelerdir?

Enterpolasyon aramasının en kötü durum zaman karmaşıklığı O(N)'dir, çünkü en kötü durumda anahtar dizinin sonunda olacağından yineleyicinin dizi boyunca hareket etmesi gerekir.
Öğe dizinin herhangi bir yerinde olabileceğinden, ortalama durum karmaşıklığı O(log(log N) olacaktır.Başlangıç noktasına da yakın olabilir.
En iyi durumda karmaşıklık O(1) olacaktır, çünkü en iyi durumda anahtar dizinin ilk elemanı olacaktır.