А>>На С++ можно вот так, а как на С?

На Си, если у тебя отсортированный массив строк, делается так же.
Только алгоритм lower_bound нужно перепереть

char const* lower_bound(char const* begin, char const* end, char const* str)
{
    // [begin,end) - диапазон поиска
    while(begin != end)
    {
        char const* median = begin + (end-begin)/2; // begin <= median < end
        if(strcmp(median,str)<0)
            begin = median+1;
        else
            end = median;
    }
}