Doğrusal arama ile ikili arama arasındaki en büyük fark, ikili aramanın, bir elemanın sıralanmış elemanlar listesinden aranmasının daha az zaman almasıdır. Dolayısıyla, ikili arama yönteminin verimliliğinin doğrusal aramadan daha büyük olduğu sonucuna varılmıştır.
İkisi arasındaki diğer bir fark, ikili arama için bir önkoşul olduğu, yani doğrusal aramada böyle bir önkoşul olmadığı sürece elemanların sıralanması gerektiğidir. Her iki arama yöntemi de aşağıda tartışılan farklı teknikleri kullanmasına rağmen.
Karşılaştırma Tablosu
| Karşılaştırma için temel | Doğrusal arama | Ikili arama |
|---|---|---|
| Zaman Karmaşıklığı | O (N) | O (log 2 N) |
| En iyi durum zamanı | İlk Öğe O (1) | Orta Eleman O (1) |
| Bir dizi için ön koşul | Gerekli değil | Dizi sıralı olmalıdır |
| N eleman sayısı için en kötü durum | N karşılaştırma gerekli | Sadece 2 N karşılaştırması yapıldıktan sonra sonuçlandırabilir. |
| Uygulanabilir | Dizi ve Bağlantılı liste | Bağlantılı listede doğrudan uygulanamaz |
| İşlem ekle | Listenin sonuna kolayca eklenir | Sıralanmış bir liste tutmak için doğru yere yerleştirmek için işlem yapılmasını gerektirir. |
| Algoritma türü | Doğada yinelemeli | Doğada bölün ve fethetmek |
| kullanışlılık | Kullanımı kolay ve sipariş verilen herhangi bir elemana gerek yok. | Her şekilde zor algoritma ve öğeler sırayla düzenlenmelidir. |
| Kod satırları | Az | Daha |
Doğrusal aramanın tanımı
Doğrusal bir aramada, bir dizinin her bir elemanı birer birer mantıksal olarak alınır ve istenen elemanın olup olmadığı kontrol edilir. Tüm öğelere erişilirse ve istenen öğe bulunmazsa, arama başarısız olur. En kötü durumda, ortalama bir vaka sayısı, dizinin boyutunun yarısını taramamız gerekebilir (n / 2).
Bu nedenle doğrusal arama, verilen öğeyi bulmak için diziyi sıralı olarak geçen teknik olarak tanımlanabilir. Aşağıda verilen program, aramayı kullanarak dizinin bir elemanının aranmasını göstermektedir.
Doğrusal aramanın etkinliği
Bir arama tablosunda bir kayıt ararken yapılan zaman tüketimi veya karşılaştırma sayısı tekniğin etkinliğini belirler. İstenilen kayıt, arama tablosunun birinci konumunda mevcutsa, sadece bir karşılaştırma yapılır. İstenilen kayıt en son kayıt olunca n karşılaştırması yapılmalıdır. Kayıt, arama tablosunda bir yerde sunulacaksa, ortalama olarak, karşılaştırma sayısı (n + 1/2) olacaktır. Bu tekniğin en kötü durum verimi O (n) 'nin yürütme sırası anlamına gelir.
C Doğrusal arama tekniği ile bir eleman aramak için program .
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nEklentinin sayısını girin:"); scanf ("% d", & n); printf ("Rakamları girin: \ n"); (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ n Aranacak numarayı girin:"); scanf ("% d", & öğe); (i = 0; i = 0) {printf ("\ n% d, % d:" konumunda bulunur, item, loc + 1); } else {printf ("\ n Öğe yok"); } getch (); } İkili aramanın tanımı
İkili arama, son derece verimli bir algoritmadır. Bu arama tekniği verilen öğeyi aramaya minimum olası karşılaştırmalarda daha az zaman harcar. İkili arama yapmak için önce dizi elemanlarını sıralamamız gerekir.
Bu tekniğin arkasındaki mantık aşağıda verilmiştir:
- İlk olarak dizinin orta elemanını bulun.
- Dizinin orta elemanı, aranacak elemanla karşılaştırılır.
Ortaya çıkabilecek üç vaka vardır:
- Öğe gerekli öğe ise, arama başarılı olur.
- Öğe istenen öğeden küçük olduğunda, dizinin yalnızca ilk yarısını arayın.
- İstenilen öğeden büyükse, dizinin ikinci yarısında arayın.
Bir öğe bulunana veya arama alanında bitinceye kadar aynı adımları tekrarlayın. Bu algoritmada, her zaman arama alanı azalmaktadır. Bu nedenle karşılaştırma sayısı en fazla log (N + 1). Sonuç olarak, doğrusal aramaya kıyasla verimli bir algoritmadır, ancak ikili aramayı yapmadan önce dizinin sıralanması gerekir.
C İkili arama tekniğiyle bir eleman bulma programı .
#include void main () {int i, dilenmek, son, orta, n, arama, dizi [100]; printf ("\ n elemanı sayısını giriniz"); scanf ( "% d" ve n); printf ("% d sayılarını girin \ n", n); (i = 0; i <n; i ++) scanf ("% d", & dizi [i]); printf ("Aranacak numarayı girin \ n"); scanf ("% d", & arama); dilenmek = 0; son = n - 1; orta = (dilenci + bitiş) / 2; while (beg <= end) {if (array [middle] end) printf ("Arama başarısız!% d listede yok. \ n", arama); getch (); } Doğrusal Arama ve İkili Arama Arasındaki Temel Farklılıklar
- Doğrusal arama, doğada yinelemelidir ve sıralı yaklaşımı kullanır. Öte yandan, İkili arama, bölme ve ele geçirme yaklaşımını uygular.
- İkili aramada O (log 2 N) varken doğrusal aramanın zaman karmaşıklığı O (N) 'dir.
- Doğrusal aramada en uygun durum, ilk eleman için, yani O (1). Karşılık olarak, ikili aramada, orta eleman içindir, yani O (1).
- Doğrusal aramada, bir elemanı aramak için en kötü durum N karşılaştırmasıdır. Buna karşılık, ikili arama için log 2 N karşılaştırma sayısıdır.
- Doğrusal arama, bir dizinin yanı sıra bağlantılı listede de uygulanabilir; bununla birlikte ikili arama doğrudan bağlantılı listede uygulanamaz.
- Bildiğimiz gibi İkili arama, dizili bir diziyi gerektirir, bu da dizilmiş bir listeyi sürdürmek için uygun yerine yerleştirmek için işlem yapılmasını gerektirir. Aksine, doğrusal arama sıralama öğeleri gerektirmediğinden, öğeler listenin sonuna kolayca eklenir.
- Doğrusal arama kullanımı kolaydır ve sipariş edilen herhangi bir öğeye gerek yoktur. Öte yandan, İkili arama algoritması çok zordur ve öğeler mutlaka sırayla düzenlenir.
Sonuç
Hem doğrusal hem de ikili arama algoritmaları, uygulamaya bağlı olarak yararlı olabilir. Bir dizi veri yapısıysa ve öğeler sıralanmış bir düzende sıralandığında, hızlı arama için ikili arama tercih edilir. Bağlantılı liste, elemanların nasıl düzenlendiğine bakılmaksızın, veri yapısı ise, ikili arama algoritmasının doğrudan uygulanamaması nedeniyle doğrusal arama benimsenir.
Tipik İkili arama algoritması, bağlantılı listeye kullanılamaz çünkü bağlantılı liste doğada dinamiktir ve orta elemanın gerçekte nerede atandığı bilinmemektedir. Bu nedenle, ikili arama arama yürütme sırasında doğrusal bir aramadan daha hızlı olduğundan, bağlantılı listede de çalışabilen ikili arama algoritmasının varyasyonunu tasarlama zorunluluğu vardır.
