İkili Arama algoritması, böl ve yönet paradigmasını takip eder. Alandan tasarruf sağlayan yöntemi kullanarak sıralanmış bir dizideki öğeleri nasıl arayacağınızı öğrenin.
Bilgisayar bilimindeki en temel algoritmalardan biri Binary Search algoritmasıdır. İkili Aramayı iki yöntem kullanarak uygulayabilirsiniz: yinelemeli yöntem ve özyinelemeli yöntem. Her iki yöntem de aynı zaman karmaşıklığına sahipken, yinelemeli yöntem uzay karmaşıklığı açısından çok daha verimlidir.
Yinelemeli yöntem , özyinelemeli yöntem tarafından üretilen O(logn) ile karşılaştırıldığında O(1) uzay karmaşıklığına sahiptir . 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 ortadaki öğ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 daha küçük demektir. Böylece kontrol, alt limiti ortadaki elemanın bir sonraki konumuna yükselterek (dizi artan sıradaysa) dizinin sağ tarafına kayar.
Benzer şekilde, arama elemanı ortadaki elemandan daha küçükse, sağ taraftaki tüm elemanlar arama elemanından daha büyük demektir. Böylece kontrol, üst limiti orta elemanın önceki konumuna değiştirerek dizinin sol kısmına kayar.
Bu, karşılaştırma sayısının en kötü durum senaryosundaki öğe sayısına eşit olduğu doğrusal arama uygulamasına kıyasla karşılaştırma sayısını büyük ölçüde azaltır . Bu yöntem, bir telefon rehberindeki sayıları veya sözlükteki sözcükleri bulmak için çok kullanışlıdır.
İşte İkili Arama algoritmasının şematik bir temsili :
- İkili Arama Algoritmasının şematik gösterimi
- C Kullanarak İkili Arama
C kullanarak İkili Arama uygulamak için şu adımları izleyin:
C, C++, Java ve Python kullanan İkili Arama Programının tüm kaynak kodu bu GitHub deposunda bulunur.
Program, bulunan değerin dizinini veya mevcut değilse -1’i döndüren binarySearch() işlevini tanımlar :
#include <stdio.h>
int binarySearch(int arr[], int arr_size, int search_number) {
/* … */
}
İşlev, arama alanını yinelemeli olarak daraltarak çalışır. İkili arama sıralanmış diziler üzerinde çalıştığından, aksi takdirde bir anlam ifade etmeyen ortayı hesaplayabilirsiniz. Kullanıcıdan sıralanmış bir dizi isteyebilir veya Bubble veya Selection sort gibi sıralama algoritmalarını kullanabilirsiniz.
Düşük ve yüksek değişkenler, mevcut arama alanının sınırlarını temsil eden dizinleri depolar . mid , endeksi ortada saklar:
int low = 0, high = arr_size – 1, mid;
Ana while() döngüsü arama alanını daraltır. Düşük indeksin değeri, yüksek indeksten daha büyük olursa, arama alanı tükenir, bu nedenle değer mevcut olamaz.
while (low <= high) {
/* continues… [1] */
}
return -1;
Döngünün başlangıcındaki orta noktayı güncelledikten sonra, üç olası sonuç vardır:
- Orta noktadaki değer aradığımız değerse, o dizini döndürün.
- Orta nokta değeri aradığımız değerden büyükse, yüksek değeri azaltın.
- Orta nokta değeri daha düşükse, düşük değeri artırın.
/* [1] …continued */
mid = (low + (high – low)) / 2;
if (arr[mid] == search_number)
return mid;
else if (arr[mid] > search_number)
high = mid – 1;
else
low = mid + 1;
Fonksiyonu kullanıcı girişi ile test edin. Dizi boyutu, içeriği ve aranacak bir sayı dahil olmak üzere komut satırından girdi almak için scanf() kullanın :
int main() {
int arr[100], i, arr_size, search_number;
printf(“Enter number of elements: “);
scanf(“%d”, &arr_size);
printf(“Please enter numbers: “);
for (i = 0; i < arr_size; i++) {
scanf(“%d”, &arr[i]);
}
printf(“Enter number to be searched: “);
scanf(“%d”, &search_number);
i = binarySearch(arr, arr_size, search_number);
if (i==-1)
printf(“Number not present”);
else
printf(“Number is present at position %d”, i + 1);
return 0;
}
Numarayı bulursanız, konumunu veya dizinini görüntüleyin, aksi takdirde numaranın bulunmadığını belirten bir mesaj.
C++ Kullanarak İkili Arama
Girdi Çıktı Akışını içe aktararak C programını bir C++ programına dönüştürebilir ve program boyunca birden çok kez tekrar etmekten kaçınmak için std ad alanını kullanabilirsiniz .
#include <iostream>
using namespace std;
printf() yerine << çıkarma operatörü ile cout ve scanf() yerine ekleme operatörü >> ile cin kullanın ve C++ programınız hazır.
printf(“Enter number of elements: “);
cout << “Enter number of elements: “;
scanf(“%d”, &arr_size);
cin >> arr_size;
Python Kullanarak İkili Arama
Python’un diziler için dahili desteği olmadığı için listeleri kullanın. Üç parametreyi, listeyi, boyutunu ve aranacak bir sayıyı kabul eden bir işlev, binarySearch() tanımlayın:
def binarySearch(arr, arr_size, search_number):
low = 0
high = arr_size – 1
while low <= high:
mid = low + (high-low)//2
if arr[mid] == search_number:
return mid
elif arr[mid] > search_number:
high = mid – 1
else:
low = mid + 1
return -1
Listenin alt ve üst sınırı olarak hizmet etmek için low ve high olmak üzere iki değişkeni başlatın. C uygulamasına benzer şekilde, arama alanını daraltan bir süre döngüsü kullanın. Listenin orta değerini saklamak için mid’i başlatın. Python, mümkün olan en büyük tamsayıyı sağlayan kat bölme operatörünü(//) sağlar.
Karşılaştırmaları yapın ve orta değer arama sayısına eşit olana kadar arama alanını daraltın. Arama numarası mevcut değilse, kontrol -1 değerini döndürür.
arr_size = int(input(“Enter number of elements: “))
arr=[]
print(“Please enter numbers: “, end=” “)
for i in range(0,arr_size):
arr.append(int(input()))
search_number = int(input(“Enter number to be searched: “))
result = binarySearch(arr, arr_size, search_number)
if result == -1:
print(“Number not present”)
else:
print(“Number is present at position “, (result + 1))
Fonksiyonu kullanıcı girişi ile test edin. Liste boyutunu, içeriğini ve aranacak sayıyı almak için input() işlevini kullanın . Python tarafından varsayılan olarak kabul edilen dize girişini bir tamsayıya yazmak için int() kullanın . Listeye sayı eklemek için append() işlevini kullanın.
binarySearch()’ i çağırın ve argümanları iletin. Numarayı bulursanız, konumunu veya dizinini görüntüleyin, aksi takdirde numaranın bulunmadığını belirten bir mesaj.
Temel Veri Yapılarını ve Algoritmaları Öğrenin
Arama, öğrendiğiniz ilk algoritmalardan biridir ve genellikle kodlama yarışmalarında, yerleştirmelerde ve röportajlarda sorulur. Öğrenmeniz gereken diğer bazı algoritmalar ise sıralama, karma, dinamik programlama, dizi eşleştirme ve asallık testi algoritmalarıdır.
Ek olarak, algoritmaların zaman ve uzay karmaşıklığını anlamak önemlidir. Herhangi bir algoritmanın verimliliğini belirlemede Bilgisayar Bilimindeki en önemli kavramlardan biridir. Veri Yapıları ve Algoritmalar bilgisi ile en iyi programları oluşturmak zorundasınız.