lower_bound, upper_bound and Searching the Answer

The standard library does it for you

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 2, 3, 5};
    int first = lower_bound(v.begin(), v.end(), 2) - v.begin();
    int after = upper_bound(v.begin(), v.end(), 2) - v.begin();
    cout << "first 2 at " << first << ", copies of 2: " << after - first << endl;
    cout << "4 would go at " << lower_bound(v.begin(), v.end(), 4) - v.begin() << endl;
    cout << "has 5? " << binary_search(v.begin(), v.end(), 5) << endl;
    return 0;
}

Output

first 2 at 1, copies of 2: 3
4 would go at 5
has 5? 1

Subtracting v.begin() turns the iterator into an index.

Binary search on the answer

If the answer is a number and you can check “is this guess too big?”, binary search the answer itself. Integer square root without sqrt:

#include <iostream>
using namespace std;

long long intSqrt(long long n) {
    long long low = 0, high = 2000000000LL;
    while (low < high) {
        long long mid = low + (high - low + 1) / 2;
        if (mid <= n / mid) low = mid;     // mid*mid <= n, written so it can't overflow
        else high = mid - 1;
    }
    return low;
}

int main() {
    cout << intSqrt(50) << " " << intSqrt(1000000) << " " << intSqrt(1000000000000000000LL) << endl;
    return 0;
}

Output

7 1000 1000000000

Remember: Binary search needs answers shaped like no, no, no, yes, yes. Then it finds the switch point in O(log n).