Бинарный поиск с счётчиком

Если массив отсортировать, то std::equal_range сделает именно то, что вам надо

int a[] = { 1, 1, 2, 2, 4, 4, 4, 4, 4 };
auto range = std::equal_range(std::begin(a), std::end(a), 4);
std::cout << range.second - range.first << std::endl;

На самом деле std::equal_range не требует строгой сортированности входного массива. Ей достаточно лишь, чтобы массив был partitioned по искомому значению.

Однако если вы возьметесь делать std::partition, то оно вам и так даст требуемый диапазон без полной сортировки массива

 int a[] = { 1, 2, 4, 4, 5, 4, 2, 4, 1, 4 };
 auto lo = std::partition(std::begin(a), std::end(a), [](int i) { return i < 4; });
 auto hi = std::partition(lo, std::end(a), [](int i) { return i < 5; });
 std::cout << hi - lo << std::endl;

Хотя все это имеет смысл только потому, что условие без объяснения причин настаивает на использовании какого-то "бинарного поиска".

Чтобы за логарифмическое время искать повторяющиеся элементы в массиве, можно использовать std::multiset<>:

#include <iterator>
#include <iostream>
#include <set>
int main()
{
  int a[] = {1, 2, 4, 4, 4, 2, 4, 1, 4};
  std::multiset<int> S {std::begin(a), std::end(a)};
  std::cout << S.count(4) << std::endl;
}

Элементы хранятся в отсортированном порядке. Временна́я сложность S.count() логарифмическая по длине массива и линейная по количеству найденных совпадений (элементов эквивалентных (!(a<b) and !(b<a)) заданному ключу).

Если каждый раз новый массив задаётся, то лучше чем O(n) нельзя поиск сделать:

#include <algorithm>
#include <iterator>
#include <iostream>
int main()
{
  int a[] = {1, 2, 4, 4, 4, 2, 4, 1, 4};
  std::cout << std::count(std::begin(a), std::end(a), 4) << std::endl;
}