İkili arama algoritması

İkili arama (), 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  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 yle 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 
küçükresim|top|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 

Kategori:Arama algoritmaları
Kategori:Algoritmalar