Bilgisayar bilimindeki en temel algoritmalardan biri İkili Arama algoritmasıdır. İkili Aramayı iki yöntem kullanarak uygulayabilirsiniz: yinelemeli yöntem ve yinelemeli yöntem. Her iki yöntem de aynı zaman karmaşıklığına sahipken, iteratif yöntem uzay karmaşıklığı açısından çok daha verimlidir.

Yinelemeli yöntemin bir uzay karmaşıklığı vardır O(1) ile karşılaştırıldığında O(oturum aç) özyinelemeli yöntemle üretilir. Peki, C, C++ ve Python'da yinelemeli yöntemi kullanarak İkili Arama algoritmasını nasıl uygulayabilirsiniz?

İkili Arama Nedir?

Yarım aralıklı arama, logaritmik arama veya ikili kesme olarak da bilinen ikili arama, sıralanmış bir dizideki bir öğenin konumunu arayan ve döndüren bir algoritmadır. Arama öğesi, orta öğeyle karşılaştırılır. Alt ve üst limitlerin ortalamasını alarak ortadaki elemanları bulabilirsiniz.

Arama elemanı ortadaki elemandan büyükse sol taraftaki tüm elemanlar arama elemanından küçük demektir. Böylece kontrol, alt limiti orta elemanın bir sonraki konumuna yükselterek (dizi artan sıradaysa) dizinin sağ tarafına kayar.

instagram viewer

Aynı şekilde arama elemanı ortadaki elemandan küçükse sağ taraftaki tüm elemanlar arama elemanından büyük demektir. Böylece kontrol, üst limiti orta elemanın bir önceki konumuna değiştirerek dizinin sol tarafına kayar.

Bu, kıyaslama sayısını önemli ölçüde azaltır. doğrusal arama uygulaması burada karşılaştırma sayısı en kötü durum senaryosundaki öğelerin sayısına eşittir. Bu yöntem, bir telefon defterindeki sayıları veya bir sözlükteki sözcükleri bulmak için çok yararlıdır.

İşte şematik bir gösterimi İkili Arama algoritması:

C Kullanarak İkili Arama

C'yi kullanarak İkili Aramayı uygulamak için şu adımları izleyin:

C, C++, Java ve Python kullanan İkili Arama Programının tüm kaynak kodu bu dosyada mevcuttur. GitHub deposu.

Program bir fonksiyon tanımlar, Ikili arama(), bulunan değerin dizinini döndürür veya -1 mevcut değilse:

#katmak <stdio.h>

intIkili arama(int dizi[], int dizi_size, int arama_numarası){
/*... */
}

İşlev, arama alanını yinelemeli olarak daraltarak çalışır. İkili arama, sıralanmış dizilerde çalıştığından, başka türlü bir anlam ifade etmeyen ortayı hesaplayabilirsiniz. Kullanıcıdan sıralanmış bir dizi isteyebilir veya Kabarcık veya Seçim sıralaması gibi sıralama algoritmalarını kullanabilirsiniz.

bu Düşük Ve yüksek değişkenler, geçerli arama alanının sınırlarını temsil eden dizinleri saklar. orta dizini ortada saklar:

int düşük = 0, yüksek = arr_size - 1, orta;

Ana sırasında() döngü, arama alanını daraltacaktır. Düşük indeksin değeri, yüksek indeksten daha büyük olursa, arama alanı tükenmiştir, bu nedenle değer mevcut olamaz.

sırasında (düşük <= yüksek) {
/* devam ediyor... [1] */
}

geri dönmek-1;

Döngünün başlangıcındaki orta noktayı güncelledikten sonra, üç olası sonuç vardır:

  1. Orta noktadaki değer aradığımız değerse, o dizini döndürün.
  2. Orta nokta değeri aradığımız değerden büyükse, yüksek değeri azaltın.
  3. Orta nokta değeri daha azsa, düşük değeri artırın.
/* [1] ...devamı */
orta = (düşük + (yüksek - düşük)) / 2;

if (dizi[orta] == arama_numarası)
geri dönmek orta;
başkaeğer (arr[orta] > arama_numarası)
yüksek = orta - 1;
başka
düşük = orta + 1;

Fonksiyonu kullanıcı girişi ile test edin. Kullanmak taramak() dizi boyutu, içeriği ve aranacak bir sayı dahil olmak üzere komut satırından girdi almak için:

intana(){
int yer[100], ben, dizi_boyutu, arama_numarası;
printf("Öğe sayısını girin: ");
taramak("%D", &dizi_size);
printf("Lütfen sayıları girin: ");

için (i = 0; Ben < dizi_size; ben++) {
taramak("%D", &dizi[i]);
}

printf("Aranacak numarayı girin: ");
taramak("%D", &arama_numarası);

i = BinarySearch (dizi, dizi_boyutu, arama_numarası);

eğer (i==-1)
printf("Numara mevcut değil");
başka
printf("Numara %d konumunda mevcut", ben + 1);

geri dönmek0;
}

Numarayı bulursanız, konumunu veya dizinini görüntüleyin, aksi takdirde numaranın mevcut olmadığını belirten bir mesaj.

C++ Kullanarak İkili Arama

C programını içe aktararak bir C++ programına dönüştürebilirsiniz. Giriş Çıkış Akışı Ve ad alanı std'sini kullan program boyunca birden çok kez tekrarlamaktan kaçınmak için.

#katmak <io akışı>
kullanarak ad alanıstd;

Kullanmak cout çıkarma operatörü ile << yerine printf() Ve cin ekleme operatörü ile >> yerine taramak() ve C++ programınız hazır.

printf("Öğe sayısını girin: ");
cout <<"Öğe sayısını girin: ";
taramak("%D", &dizi_size);
cin >> dizi_size;

Python Kullanarak İkili Arama

Python'un diziler için yerleşik desteği olmadığından, listeleri kullanın. Bir işlev tanımlayın, Ikili arama(), liste, boyutu ve aranacak bir sayı olmak üzere üç parametreyi kabul eder:

kesinIkili arama(dizi, dizi_boyutu, arama_numarası):
düşük = 0
yüksek = arr_size - 1
sırasında düşük <= yüksek:
orta = düşük + (yüksek-düşük)//2
dizi[orta] == arama_numarası ise:
geri dönmek orta
elif dizi[orta] > arama_numarası:
yüksek = orta - 1
başka:
düşük = orta + 1
geri dönmek-1

İki değişkeni başlat, Düşük Ve yüksek, listenin alt ve üst sınırı olarak işlev görür. C uygulamasına benzer şekilde, bir sırasında arama alanını daraltan döngü. Başlat orta Listenin orta değerini saklamak için. Python, mümkün olan en büyük tamsayıyı sağlayan taban bölme operatörünü (//) sağlar.

Karşılaştırmaları yapın ve ortadaki değer arama numarasına eşit olana kadar arama alanını daraltın. Arama numarası mevcut değilse, kontrol geri dönecektir. -1.

dizi_boyutu = int (giriş("Öğe sayısını girin: "))
dizi=[]
Yazdır("Lütfen sayıları girin: ", bitiş="")
aralıktaki i için (0,arr_size):
dizi.ekleme(int(giriş()))
arama_numarası = int (giriş("Aranacak numarayı girin: "))
sonuç = ikili Arama (dizi, dizi_boyutu, arama_numarası)
sonuç == -1 ise:
Yazdır("Numara mevcut değil")
başka:
yazdır("Sayı dır-dir " konumunda mevcut, (sonuç + 1))

Fonksiyonu kullanıcı girişi ile test edin. Kullanmak giriş() liste boyutunu, içeriğini ve aranacak bir numarayı almak için. Kullanmak int() Python tarafından varsayılan olarak kabul edilen dize girişini bir tamsayıya yazmak için. Listeye numara eklemek için, ekle() işlev.

Arama Ikili arama() ve bağımsız değişkenleri iletin. Numarayı bulursanız, konumunu veya dizinini görüntüleyin, aksi takdirde numaranın mevcut olmadığını belirten bir mesaj.

İkili Arama Algoritmasının Çıktısı

Öğe dizide mevcut olduğunda İkili Arama algoritmasının çıktısı aşağıdadır:

Öğe dizide olmadığında İkili Arama algoritmasının çıktısı aşağıdadır:

Temel Veri Yapılarını ve Algoritmalarını Öğrenin

Arama, öğrendiğiniz ilk algoritmalardan biridir ve genellikle kodlama yarışmalarında, yerleştirmelerde ve mülakatlarda sorulur. Öğrenmeniz gereken diğer bazı algoritmalar sıralama, karma, dinamik programlama, dizi eşleştirme ve asallık testi algoritmalarıdır.

Ek olarak, algoritmaların zaman ve mekan karmaşıklığını anlamak önemlidir. Herhangi bir algoritmanın verimliliğini belirlemede Bilgisayar Bilimindeki en önemli kavramlardan biridir. Veri Yapıları ve Algoritmalar bilgisiyle, en iyi programları oluşturmak zorundasınız.