İkili arama algoritması

İkili arama algoritması
İkili arama algoritması
	İkili aramayla 7 aranırken algoritmanın izlediği yol
Sınıf	Arama algoritması
Veri yapısı	Dizi
Zaman karmaşıklığı
En iyi
Ortalama
Alan karmaşıklığı

İkili Arama (Ingilizce: 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 devam eder. Her adımda dizi ikiye bölünür.

İkili arama N elemanlı bir dizide en kötü durumda $\lceil \log _{2}N\rceil$ karşılaştırma yapar. İkili arama yöntemi, bir elemanın yerini bulmak için dizinin bütün elemanlarını tek tek kontrol eden kaba kuvvet yönteminden zaman ve bellek açısından daha tasarrufludur. İkili aramayla, 7 elemanlı veride sonuca 3 adımda ulaşır, 7000000 elemanlı veride yalnızca 23 adımda tamamlanır.

Örnekler

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