Линейный поиск, бинарный поиск. Сравнение эффективности. Реализация на C.

September 10, 2018 23:23

Двоичный или бинарный поиск - один из эффективных и очень мощных методов. И понять это, весьма, несложно. Разберем на простом примере: есть массив из 1023 элементов. После первого прохода алгоритма область сравнения сужается до 511 элементов. Каждый последующий раз уменьшает эту область еще в два раза. Следовательно на поиск элемента уйдет всего 10 сравнений.

Линейный (последовательный поиск) - это алгоритм нахождения значения произвольной функции на определенном отрезке. Является одним из простейших алгоритмов поиска. Поиск значения функции осуществляется сравнением очередного рассматриваемого значения и, если значения совпадают, то поиск считается завершённым.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Линейный и бинарный поиск, сравнение их эффективности 

typedef unsigned int arr_type;

unsigned int linearSearch(const arr_type key, const unsigned int len, arr_type *arr) {
    unsigned int i = 0;
    while ((arr[i] != key) && (i < len)) i++;
    return i;
}

unsigned int linearSearchBlock(const arr_type key, const unsigned int len, arr_type *arr) {
    unsigned int i = 0;
    arr[len - 1] = key;
    while (arr[i] != key) i++;
    return (i == len - 1) ? -1 : i;
}

unsigned int binSearch(const arr_type key, const unsigned int len, arr_type *arr) {
    unsigned int m,l,r;
    l = 0;
    r = len - 1;

    while (l < r) {
        m = (l + r) / 2;
        if (key > arr[m]) l = m + 1;
        else r = m; 
    }
    return (arr[l] == key) ? l : -1;  
}

unsigned int linearSearchCount(const arr_type key, const unsigned int len, arr_type *arr, unsigned int *count) {
    unsigned int i = 0;
    (*count) = 0;
    while (((*count)++ ,arr[i] != key ) && ((*count)++, i < len)) i++;
    return i;
}

unsigned int linearSearchBlockCount(const arr_type key, const unsigned int len, arr_type *arr, unsigned int *count) {
    unsigned int i = 0;
    (*count) = 0;
    arr[len - 1] = key;
    while ((*count)++, arr[i] != key) i++;
    return ((*count)++, i == len - 1) ? -1 : i;
}

unsigned int binSearchCount(const arr_type key, const unsigned int len, arr_type *arr, unsigned int *count) {
    unsigned int m,l,r,i = 0;
    l = 0;
    r = len - 1;
    (*count) = 0; 
    while ((*count)++, l < r) {
        m = (l + r) / 2;
        if ((*count)++, key > arr[m]) l = m + 1;
        else r = m;
    }
    return ((*count)++, arr[l] == key) ? l : -1;  
}

int main(int argc, char const *argv[]) {

    const int size[] = { 
        100000000, 200000000, 300000000, 400000000, 500000000, 
    };

    arr_type *array;
    arr_type key = atoi(argv[1]);
    
    clock_t time;
    unsigned int val;
    unsigned int count; 

    for (int i = 0; i < 5; ++i) {
    
        if(!(array = malloc(sizeof(arr_type)*size[i]))) return -1;

        for (int j = 0; j < size[i]; ++j) array[j] = j; 

        printf("[%10d]\n\t\t ITER\t   TIME\n",size[i]);
        
        time = clock(); 
        linearSearch(key, size[i], array); 
        time = clock() - time;    
        
        linearSearchCount(key, size[i], array, &count);
        printf("\tLIN:\t%10u %.3f\n", count, (double) time / CLOCKS_PER_SEC);

        if (!(array = realloc(array, sizeof(arr_type)*size[i] + sizeof(arr_type)))) { 
                free(array);
                return -2;
        }
        
        time = clock();
        linearSearchBlock(key, size[i] + 1, array);
        time = clock() - time;

        linearSearchBlockCount(key, size[i] + 1, array, &count);
        printf("\tLINB:\t%10u %.3f\n", count, (double) time / CLOCKS_PER_SEC);

        
        time = clock();
        binSearch(key, size[i], array);
        time = clock() - time;

        binSearchCount(key, size[i], array, &count);
        printf("\tBIN:\t%10u %.3f\n\n", count, (double) time / CLOCKS_PER_SEC);

        free(array);
    }    

    return 0;
}