Binary Search

Kategori: C , 02 Temmuz 2019 , JanFranco


Binary search algoritması, linear search algoritmasına göre çok daha hızlı ve etkilidir. Sayının arandığı dizi sıralı olmalıdır. Algoritma adım adım şu şekilde işler:

1. Dizi ortadan ikiye bölünür.
2. Ortadaki sayı ile aranan sayı kontrol edilir.
3. Eğer aranan sayı ortadaki sayıya eşitse arama sonlanır. Eğer aranan sayı ortadaki sayıdan büyükse dizinin sağ tarafına aynı işlemler uygulanır. Eğer aranan sayı ortadaki sayıdan küçükse dizinin sol tarafına aynı işlemler uygulanır.

Görüldüğü gibi recursive bir algoritmadır. Nasıl kullanacağımızı görelim:


#include <stdio.h>

int binary_search_(int arr[], int start, int finish, int number){
    if(finish >= start){
        int middle = ((finish - start) / 2) + start;
        printf("middle: %d\n", middle);
        if(arr[middle] == number)
            return middle;
        else if(arr[middle] > number)
            return binary_search_(arr, start, middle - 1, number);
        return binary_search_(arr, middle + 1, finish, number);
    }
    return -1;
}

int main() {

    int i, length, arr[10000];
    for(i=0; i<10000; i++){
        arr[i] = i;
    }
    length = sizeof(arr) / sizeof(arr[0]);

    int result = binary_search_(arr, 0, length, 5000);

    if(result == -1)
        printf("Not found!");
    else{
        printf("Found at %d\n", result);
        printf("arr[%d] = %d", result, arr[result]);
    }

    return 0;
}

Dizinin boyutunu değiştirerek veya aranacak sayıyı değiştirerek sonuçları yani hızları karşılaştırabiliriz.


Sonraki Yazı: Bubble Sort
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın