dichotomy.h

#pragma once

namespace csl {

template<class Iterator, class Comparator> 
Iterator dichotomyFindIf(
        Iterator     first,
        Iterator     last,
        Comparator &&f
        )
{
    while (last != first) {
        const auto diff = last - first;
        Iterator mid = first + diff/2;
        // auto const &midExpr = v[mid]->getEncapsulated();
        int comp = f(*mid);
        if (comp == 1)
            last = mid;
        else if (comp == -1) {
            if (mid == first)
                ++first;
            else
                first = mid;
        }
        else
            return mid;
        if (first + 1 == mid) {
            return (f(*first) == 1) ? first : mid;
        }
    }
    return first;
}

}