İkili Arama Algoritması

İkili Arama, sıralanmış bir dizideki bir elemanın konumunu bulmak için kullanılan bir arama algoritmasıdır. Bu yaklaşımda, eleman her zaman dizinin bir bölümünün ortasında aranır. 

İkili arama yalnızca sıralanmış bir öğe listesi üzerinde uygulanabilir. Öğeler zaten sıralanmamış ise, öncelikle sıralanmaları gerekmektedir. 

Çalışma Mantığı

İkili Arama algoritması iki şekilde uygulanabilir. 

• Özyinelemeli (Recursive) Yaklaşım 
• Yinelemeli (Iterative) Yaklaşım 

Özyinelemeli yaklaşım böl ve yönet mantığını benimsese de genel olarak iki yaklaşım da şu adımlardan oluşmaktadır:

1.Adım:

Dizi sıralanmış bir halde ve aranacak eleman 4 olsun. 

2. Adım: 

Dizinin en küçük ve en büyük elemanı bulunur. 

3. Adım:

Dizinin ortanca elemanı bulunur. 

ortanca eleman = (en küçük eleman + en büyük eleman)/2

4.Adım: Eğer aranan eleman ortanca eleman ise aranan eleman bulunmuştur. Fakat değilse, bulunan eleman ile aranan eleman karşılaştırılır. 

5.Adım: Eğer aranan eleman ortanca elemandan büyükse, aranan eleman ortanca elemanın sağ tarafında elemanlar arasında aranmaya devam edilir. Bu durumda en küçük eleman = ortanca eleman +1 olarak ayarlanır. 

6. Adım: Aranan eleman ortanca elemandan küçükse, aranan eleman ortanca elemanın sol tarafındaki elemanlar arasında aranmaya devam edilir. Bu durumda en büyük eleman = ortanca eleman -1 olarak ayarlanır.

7.Adım: En küçük eleman ile en büyük eleman arasında bir eleman (aranan) kalana devam arama devam ettirilir.

İkili Arama Algoritması Yinelemeli Yaklaşım Pseudocode

    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) 
        low = mid + 1
    else                       
        high = mid - 1

İkili Arama Algoritması Özyinelemeli Yaklaşım Pseudocode

binarySearch(arr, x, low, high)
    if low > high
        return False 
    else
        mid = (low + high) / 2 
        if x == arr[mid]
            return mid
        else if x > arr[mid]        
            return binarySearch(arr, x, mid + 1, high)
        else                              
            return binarySearch(arr, x, low, mid - 1)

İkili Arama Algoritması Java Kodu İle

class BinarySearch {
  int binarySearch(int array[], int x, int low, int high) {

    while (low <= high) {
      int mid = low + (high - low) / 2;

      if (x == array[mid])
        return mid;

      if (x > array[mid])
        low = mid + 1;

      else
        high = mid - 1;
    }

    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int array[] = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;
    int x = 4;
    int result = ob.binarySearch(array, x, 0, n - 1);
    if (result == -1)
      System.out.println("Eleman bulunamadı.");
    else
      System.out.println("Elemana bulundu. (İndex) " + result);
  }
}