Szukanie elementu w niemalejąco posortowanej tablicy używając wyszukiwania binarnego, C++ (gcc)

Szukanie elementu w niemalejąco posortowanej tablicy używając wyszukiwania binarnego

#ifdef DEBUG
#   include <stdio.h>
#   define LOG(...) fprintf(stderr, __VA_ARGS__)
#else
#   define NDEBUG
#   define LOG(...)
#endif

#include <assert.h>

#define FIS_CHECK_CELL(WHICH) \
    if(array[WHICH] == to_find) \
        return WHICH

template <typename Array>
bool sorted(const Array& array, const int size ){
    for(unsigned i=1; i<size; ++i)
        if(array[i-1] > array[i])
            return false;
    return true;
}

template <typename Array, typename ToFind>
int find_in_sorted(const Array& array, const int arr_size, const ToFind& to_find) {
    
    assert(sorted(array, arr_size)); //tablica musi byc posortowana niemalejaco
    assert(arr_size >= 0); //jaki ma sens tablica z ujemna liczba elementow?
    
    const int not_found = -1;
    
    if(arr_size > 0) {
        int begin = 0, end = arr_size;
        while(end - begin >= 2) {
            int mid = (begin+end) / 2;
            LOG("PRZEDZIAL: <%d, %d),\tmid: %d\n", begin, end, mid);
            FIS_CHECK_CELL(mid);
            if(to_find < array[mid])
                end = mid; //array[end] nie jest sprawdzany
            else
                begin = mid+1;
        }
        /* !!!
           Następna instrukcja spowoduje Niezdefiniowane Zachowanie
           gdy jest zdefiniowane makro DEBUG, a podana tablica nie skladza sie z intow
           !!! */
        LOG("begin: %d, array[begin]: %d\n", begin, array[begin]);
        FIS_CHECK_CELL(begin);
    }
    
    /* Nie znaleziono */
    return not_found;
}

#undef FIS_CHECK_CELL

#ifdef DEBUG
    #include <iostream>
    int main() {
        int to_find;
        std::cin >> to_find;
        int testdata[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
        std::cout << find_in_sorted(testdata, 15, to_find) << '\n';
    }
#endif


run \| edit \| history \| help	0