Doğrusal ve ikili arama arasındaki farkları anlamadan önce doğrusal aramayı ve ikili aramayı ayrı ayrı bilmemiz gerekir.
Doğrusal arama nedir?
Doğrusal arama aynı zamanda her bir öğeyi aynı anda tarayan sıralı arama olarak da bilinir. Bir dizi veya listedeki bir öğeyi aramak istediğimizi varsayalım; sadece uzunluğunu hesaplıyoruz ve hiçbir öğenin üzerine atlamıyoruz.
Basit bir örnek düşünelim.
Aşağıdaki şekilde gösterildiği gibi 10 öğeden oluşan bir dizimiz olduğunu varsayalım:
Yukarıdaki şekil 10 değere sahip bir karakter tipi dizisini göstermektedir. 'E'yi aramak istersek arama 0'dan başlar.oeleman ve eleman, yani 'E' bulununcaya kadar her elemanı tarar. Doğrudan 0'dan atlayamayızo4'e kadar elemanoyani her öğe, öğe bulunamayana kadar tek tek taranır.
Doğrusal aramanın karmaşıklığı
Doğrusal arama, öğe bulunamayana kadar her öğeyi tek tek tarar. Eleman sayısı arttıkça taranacak eleman sayısı da artar. şunu söyleyebiliriz ki Elementleri aramak için harcanan zaman elementlerin sayısıyla orantılıdır . Bu nedenle en kötü durum karmaşıklığı O(n)'dir.
İkili arama nedir?
İkili arama, ortadaki öğenin, aranacak öğeden daha küçük veya daha büyük olup olmadığını kontrol etmek için hesaplandığı bir aramadır. İkili arama kullanmanın temel avantajı listedeki her öğeyi taramamasıdır. Her elemanı taramak yerine listenin yarısına kadar arama gerçekleştirir. Dolayısıyla ikili arama, doğrusal aramaya kıyasla bir öğeyi aramak için daha az zaman alır.
Bir ikili aramanın ön koşulu bir dizinin sıralı olması gerekirken, doğrusal arama hem sıralanmış hem de sıralanmamış dizide çalışır. İkili arama algoritması böl ve yönet tekniğine dayanmaktadır; bu, diziyi yinelemeli olarak böleceği anlamına gelir.
İkili aramada kullanılan üç durum vardır:
Durum 1: veriler
Durum 2: veri>a[orta] sonra sağ=orta-1
Durum 3: veri = a[mid] // eleman bulundu
Yukarıdaki durumda, ' A ' dizinin adıdır, orta yinelemeli olarak hesaplanan öğenin indeksidir, veri aranacak öğedir, sol dizinin sol elemanını belirtir ve Sağ dizinin sağ tarafında yer alan öğeyi belirtir.
Bir örnek üzerinden ikili aramanın çalışmasını anlayalım.
Aşağıdaki şekilde gösterildiği gibi 0'dan 9'a kadar indekslenen 10 boyutlu bir dizimiz olduğunu varsayalım:
Yukarıdaki diziden 70 elemanı aramak istiyoruz.
Aşama 1: Öncelikle dizinin ortadaki elemanını hesaplıyoruz. İki değişkeni, yani sol ve sağı dikkate alıyoruz. Başlangıçta aşağıdaki şekilde gösterildiği gibi sol =0 ve sağ=9:
Orta eleman değeri şu şekilde hesaplanabilir:
Dolayısıyla mid = 4 ve a[mid] = 50. Aranacak eleman 70 olduğundan a[mid] veriye eşit değildir. Durum 2 sağlanmıştır, yani veri>a[orta].
Adım 2: data>a[mid] olduğundan left'in değeri mid+1 artar, yani left=mid+1 olur. Mid değeri 4 olduğundan left değeri de 5 olur. Artık aşağıdaki şekilde gösterildiği gibi bir alt dizimiz var:
Şimdi yine yukarıdaki formül kullanılarak orta değer hesaplanır ve orta değer 7 olur. Şimdi orta şu şekilde temsil edilebilir:
Yukarıdaki şekilde a[mid]>data olduğunu görüyoruz, dolayısıyla bir sonraki adımda yine mid değeri hesaplanacak.
Aşama 3: Bir[mid]>veri olarak right'ın değeri -1'in ortasında azaltılır. mid değeri 7 olduğundan right değeri 6 olur. Dizi şu şekilde temsil edilebilir:
Mid değeri tekrar hesaplanacaktır. Sol ve sağ değerleri sırasıyla 5 ve 6'dır. Bu nedenle mid'in değeri 5'tir. Artık mid aşağıda gösterildiği gibi bir dizide temsil edilebilir:
Yukarıdaki şekilde bir[orta]
Adım 4: [orta] olarak Şimdi mid değeri daha önce tartıştığımız formül kullanılarak yeniden hesaplanır. Left ve right değerleri sırasıyla 6 ve 6 olduğundan mid değeri aşağıdaki şekilde gösterildiği gibi 6 olur: Yukarıdaki şekilde a[mid]=data olduğunu görebiliriz. Bu nedenle arama tamamlandı ve öğe başarıyla bulundu. Doğrusal arama ile ikili arama arasındaki farklar şunlardır: Tanım Doğrusal arama, listedeki bir öğeyi, öğe listede bulunana kadar sırayla arayarak bulan bir aramadır. Öte yandan, ikili arama, ortadaki öğeyi aranan öğeyle eşleştirilene kadar listedeki orta öğeyi yinelemeli olarak bulan bir aramadır. Her iki aramanın da çalışması Doğrusal arama, aramaya ilk öğeden başlar ve sonraki öğeye atlamadan her seferinde bir öğeyi tarar. Öte yandan ikili arama, dizinin orta elemanını hesaplayarak diziyi ikiye böler. Uygulama Doğrusal arama, vektör, tek bağlantılı liste, çift bağlantılı liste gibi herhangi bir doğrusal veri yapısında gerçekleştirilebilir. Buna karşılık, ikili arama, iki yönlü geçişli, yani ileri ve geri geçişli veri yapılarında uygulanabilir. Karmaşıklık Doğrusal aramanın kullanımı kolaydır veya doğrusal aramanın öğeleri herhangi bir sırada düzenlenebildiğinden daha az karmaşık olduğunu söyleyebiliriz, oysa ikili aramada öğelerin belirli bir sırada düzenlenmesi gerekir. Sıralanmış öğeler Doğrusal bir aramanın elemanları rastgele sırada düzenlenebilir. Doğrusal aramada elemanların sıralı bir şekilde düzenlenmesi zorunlu değildir. Öte yandan ikili aramada elemanların sıralı bir şekilde düzenlenmesi gerekir. Artan veya azalan sırada düzenlenebilir ve buna göre algoritma değişecektir. İkili arama sıralanmış bir dizi kullandığından, öğeyi doğru yere eklemek gerekir. Buna karşılık, doğrusal aramanın sıralanmış bir diziye ihtiyacı yoktur, böylece yeni öğe dizinin sonuna kolayca eklenebilir. Yaklaşmak Doğrusal arama, öğeyi bulmak için yinelemeli bir yaklaşım kullanır, dolayısıyla sıralı yaklaşım olarak da bilinir. Buna karşılık ikili arama, dizinin ortadaki öğesini hesaplar, dolayısıyla böl ve yönet yaklaşımını kullanır. Veri seti Doğrusal arama büyük veri seti için uygun değildir. Dizinin son elemanı olan elemanı aramak istersek, doğrusal bir arama aramaya ilk elemandan başlayıp son elemana kadar devam edeceğinden, elemanın aranması için harcanan süre büyük olacaktır. Öte yandan ikili arama, daha az zaman aldığından büyük bir veri seti için uygundur. Hız Doğrusal aramada veri seti büyükse hesaplama maliyeti yüksek olur ve hız yavaşlar. İkili aramada veri seti büyükse, hesaplama maliyeti doğrusal aramaya göre daha az olur ve hız artar. Boyutlar Doğrusal arama hem tek hem de çok boyutlu dizilerde kullanılabilirken, ikili arama yalnızca tek boyutlu dizilerde uygulanabilir. Yeterlik Büyük veri kümelerini göz önüne aldığımızda doğrusal arama daha az verimlidir. Büyük veri kümeleri söz konusu olduğunda ikili arama, doğrusal aramaya göre daha verimlidir. Farklılıklara tablo halinde bakalım. 
Doğrusal arama ile İkili arama arasındaki farklar
piton yapıcısı
Karşılaştırmanın temeli Doğrusal arama Ikili arama Tanım Doğrusal arama, aramaya ilk öğeden başlar ve öğe bulunamayana kadar her öğeyi aranan öğeyle karşılaştırır. Dizinin ortadaki elemanını bularak aranan elemanın konumunu bulur. Sıralanmış veriler Doğrusal bir aramada öğelerin sıralı bir şekilde düzenlenmesine gerek yoktur. İkili aramanın ön koşulu, elemanların sıralı bir şekilde düzenlenmesidir. Uygulama Doğrusal arama, dizi, bağlantılı liste vb. gibi herhangi bir doğrusal veri yapısına uygulanabilir. İkili aramanın uygulanması, yalnızca iki yönlü geçişe sahip veri yapılarında uygulanabileceğinden sınırlıdır. Yaklaşmak Sıralı yaklaşıma dayanmaktadır. Böl ve yönet yaklaşımına dayanmaktadır. Boyut Küçük boyutlu veri setleri için tercih edilir. Büyük boyutlu veri setleri için tercih edilir. Yeterlik Büyük boyutlu veri kümeleri durumunda daha az verimlidir. Büyük boyutlu veri kümeleri durumunda daha verimlidir. En kötü durum senaryosu Doğrusal bir aramada, öğeyi bulmak için en kötü senaryo O(n)'dir. İkili aramada, öğeyi bulmak için en kötü senaryo O(log) şeklindedir.2N). En iyi durum senaryosu Doğrusal aramada listedeki ilk öğeyi bulmak için en iyi senaryo O(1)'dir. İkili aramada listedeki ilk öğeyi bulmak için en iyi senaryo O(1)'dir. Boyutsal dizi Hem tek hem de çok boyutlu bir diziye uygulanabilir. Yalnızca çok boyutlu bir dizide uygulanabilir.