сложность алгоритма двоичного поиска находится где-то между O(1) и O(N). Так какова же она?

Временная сложность двоичного поиска выражается с помощью О-нотации так: O(log N).