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. :slight_smile:


#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.