 # Don't forget the STL

#1

In an interview, don’t code binary search if you can get away with it. Any opportunity to avoid off-by-one should be taken - you can solve this problem in 3 lines of C++ using the standard library:

``````int Solution::findCount(const vector<int> &A, int B) {

auto lower = std::lower_bound(A.begin(), A.end(), B);
auto upper = std::upper_bound(A.begin(), A.end(), B);

return std::distance(lower, upper);
}
``````

You could also use `equal_range`:

``````int Solution::findCount(const vector<int> &A, int B) {
auto range = std::equal_range(A.begin(), A.end(), B);
return std::distance(range.first, range.second);
}
``````

Writing the solution manually would require two binary searches to find the first element greater than `B` and the first element that is at least `B`. Remember that this only works if your input is sorted.

Note that `std::count` is O(n) and works on any iterable, sorted or not. For an unsorted input, you may as well just use `count`, otherwise the overhead of sorting (i.e. O(n log n)) will dominate.

#2

Thank you for sharing this useful information!
+1 for this discussion. #3

why it is giving error

int Solution::findCount(const vector &A, int B) {
const vector::iterator lower,upper;
lower = std::lower_bound(A.begin(), A.end(), B);
upper = std::upper_bound(A.begin(), A.end(), B);
return std::distance(lower, upper);
}

#4

use const_iterator inplace of iterator.