Home / Algoritmalar / Binary Search Algoritması (C kodu, python kodu, java kodu)

Binary Search Algoritması (C kodu, python kodu, java kodu)

Binary Search algoritması Lineer Search Algoritması‘ndan farklı olarak sıralı bir dizi üzerine uygulanır. Esasında recursive (öz yinelemeli) fonksiyonlar için çok iyi bir örnektir.

Binary Search algoritmasında dizi her adımda ikiye bölünür. Mantığı şu şekildedir.

  • Dizinin ortasındaki elemanı bul eğer aradığın elemana eşitse index’i döndür
  • Eğer aradığın eleman ortadaki elemandan küçükse sol tarafa bak ve ortadaki sayıyla karşılaştır
  • Eğer aradığın eleman ortadaki elemandan büyükse sağ tarafa bak ve sayıyla karşılaştır

Yukarıdaki mantık aranan eleman bulununcaya kadar devam eder.

Binary Search Algoritması Örnek

Aşağıdaki örnekte 23 sayısının arandığı var sayılmıştır.

Örneğimizi açıklayalım. Gördüğünüz üzere 10 elemanlı bir dizide aranılan sayıyı 4 adımda bulduk. Peki ama nasıl?

  • 1. Adım: Ortadaki sayı bulunur (16), 16 ile 23 karşılaştırılır 23 16’dan büyük olduğu için sağ tarafa bakılır.
  • 2. Adım: sağ tarafın ortasındaki sayı bulunur (56), baktığımızda 23’ün küçük olduğu görülür. Bu sefer 56’nın soluna bakarız.
  • 3. Adım: Ortadaki sayı direkt 23 çıkar. Bu sefer sayıyı bulmuş olduk, index’i return ederiz.

 

Binary Search C Kodu


#include <stdio.h>;
 
//Fonksiyonumuza parametre olarak dizimizi, dizinin en sol elemanını (int l)
// dizimizin en sağ elemanını (int l) ve aranılan elemanını (x) gönderiyoruz.
int binarySearch(int arr[], int l, int r, int x)
{
   //Sağ soldan büyük oldukça işlemimize devam edeceğiz.
   if (r >= l)
   {
        //Ortadaki elemanı buluyoruz
        int mid = l + (r - l)/2;
 
        // Ortanca eleman aranılan elemansa indisi return ediyoruz
        if (arr[mid] == x)  return mid;
 
        // Eğer elemanımız mid'den küçükse recursive olarak fonksiyonumuzu çağrıyoruz
        // Yani Sol tarafı artık ayrı bir dizi olarak yapılandırıyoruz
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
 
        // Eğer yukarıdaki hiçbir şart sağlanmıyorsa mid'den büyüktür demektir
        return binarySearch(arr, mid+1, r, x);
   }
 
   // Yukarıdaki hiçbir işlem gerçekleşmezse aradığımız sayı dizide yok demektir
   // Bu yüzden direkt return edip sonlandırıyoruz.
   return -1;
}

int main(void)
{
   int arr[] = {2, 3, 4, 10, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int x = 10;
   int result = binarySearch(arr, 0, n-1, x);
   (result == -1)? printf("Aradığınız element dizide bulunmuyor")
                 : printf("Aradığınız element şu indiste => %d", result);
   return 0;
}

Binary Search Python Kodu


def binarySearch (arr, l, r, x):
 
    
    if r >= l:
 
        mid = l + (r - l)/2
 
       
        if arr[mid] == x:
            return mid
         
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
 
        
        else:
            return binarySearch(arr, mid+1, r, x)
 
    else:
        return -1
 
arr = [ 2, 3, 4, 10, 40 ]
x = 10
 
result = binarySearch(arr, 0, len(arr)-1, x)
 
if result != -1:
    print "Elementimiz %d. indiste" % result
else:
    print "Aradığınız element dizide mevcut değil"

Binary Search Java Kodu


class BinarySearch
{
    int binarySearch(int arr[], int l, int r, int x)
    {
        if (r>=l)
        {
            int mid = l + (r - l)/2;

            if (arr[mid] == x)
               return mid;
 
            if (arr[mid] > x)
               return binarySearch(arr, l, mid-1, x);

            return binarySearch(arr, mid+1, r, x);
        }
 
        return -1;
    }
 
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = {2,3,4,10,40};
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr,0,n-1,x);
        if (result == -1)
            System.out.println("Element dizide yok");
        else
            System.out.println("Element şu indexte bulundu => "+result);
    }
}

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir