четверг, 30 апреля 2015 г.

Binary search

Finds an index to put a element to if it's absent. Return true if it's there. Helps to find an index to insert an element. Not content with this one. Must be somehow redone. Looks like shit actually. Requires size_t slot be initialized by '0'


bool find_slot(const char * buffer, 
const size_t size, 
const char elem, 
size_t * slot) {

    const size_t m = (size_t)(size / 2);

    if ( m == 0 )
        return false;

    if ( elem > buffer[m - 1] ) {
        *slot += m;
        if ( elem < buffer[m] )
            return false;
        return find_slot(buffer + m, size - m, elem, slot);
    }

    if ( elem < buffer[m - 1] ) {
        if ( elem > buffer[m - 2] )
            return false;
        return find_slot(buffer, size - m, elem, slot);
    }
    return true;
}

Комментариев нет:

Отправить комментарий