İkili arama algoritması

İkili arama algoritması
İkili aramayla 7 aranırken algoritmanın izlediği yol
SınıfArama algoritması
Veri yapısıDizi
Zaman karmaşıklığı O ( log ⁡ n ) {\displaystyle O(\log n)}
En iyi O ( 1 ) {\displaystyle O(1)}
Ortalama O ( log ⁡ n ) {\displaystyle O(\log n)}
Alan karmaşıklığı O ( 1 ) {\displaystyle O(1)}

İkili arama (İngilizce: Binary search), sıralı bir dizide, belirli değerin aranmasına yönelik bir algoritmadır. Her adımda, aranan değerin dizinin orta değerine eşit olup olmadığı kontrol edilir. Eşit ise aranan bulunmuştur. Aranan değer orta değerden küçükse, dizinin sıralı olduğu kabulünden, ortanın yukarısına bakmaya gerek kalmaz, arama dizinin başı ve orta değer arasında devam eder. Aranan ortadan büyükse arama orta ile son arasında devam eder. Her adımda dizi ikiye bölünür.

İkili arama N elemanlı bir dizide en kötü durumda ⌈ log 2 ⁡ N ⌉ {\displaystyle \lceil \log _{2}N\rceil } karşılaştırma yapar. Buna göre algoritma, 7 elemanlı veride sonuca 3 adımda ulaşır, 7000000 elemanlı veride, arananın yerinden bağımsız olarak, yalnızca 23 adım gereklidir. Eğer kaba kuvvet yöntemiyle dizinin her elemanı tek tek kontrol edilseydi ve aranan 7000000. indiste bulunsaydı (en kötü durum) 7000000 adım gerekli olacaktı. Bu karşın kaba kuvvet yönteminde dizinin sıralı olma şartı yoktur. Dizinin boyu küçük olduğunda doğrusal arama kullanılabilir.

Örnekler

binary-search
Binary Search

Pseudocode: 

function binary_search(A, n, T) is
    L := 0
    R := n - 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m - 1
        else:
            return m
    return unsuccessful

C++: 

#include <vector>

int search(const std::vector<int> &data, int target) {
  int left = 0;
  int right = data.size() - 1;

  while (left <= right) {
    int middle = left + (right - left) / 2;

    if (data[middle] < target)
      left = middle + 1;
    else if (data[middle] > target)
      right = middle - 1;
    else // target == data[middle]
      return middle;
  }

  return -1;
}

Java: 

public class BinarySearch {
  public static int search(int[] data, int target) {
    int left = 0;
    int right = data.length - 1;

    while (left <= right) {
      int middle = left + (right - left) / 2;

      if (data[middle] < target)
        left = middle + 1;
      else if (data[middle] > target)
        right = middle - 1;
      else
        return middle;
    }

    return -1;
  }
}

Python: 

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        middle = (left + right) // 2

        if arr[middle] < target:
            left = middle + 1
        elif arr[middle] > target:
            right = middle - 1
        else:
            return middle

    return -1

Kütüphane desteği

Pek çok programlama dili, standard kütüphanelerinde iki arama algoritmasını gerçekler. C++ standard kütüphanesi sıralı veriler üzerinde işlem yapan lower_bound, upper_bound, binary_search gibi pek çok algoritma gerçeklenimi bulundurur: 

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  std::cout << std::boolalpha
            << std::ranges::binary_search(numbers, 0)  << '\n'
            << std::ranges::binary_search(numbers, 11) << '\n'
            << std::ranges::binary_search(numbers, 5)  << '\n'
            ;
}

// false
// false
// true

Kaynakça