Binary search — basic problems
Three short patterns on a sorted array: strict membership, first position at least X, and how many times X appears.
Problem 1 — Is X in the sorted array?
Task: Given sorted a and x, print yes/no (or return index).
Idea: Find the first index with a[i] >= x. If that index is valid and a[i] == x, you found x; otherwise x is missing.
Code:
Solution 1 — code
#include <bits/stdc++.h>
using namespace std;
int first_ge(const vector<int>& a, int x) {
int lo = 0, hi = (int)a.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= x) hi = mid;
else lo = mid + 1;
}
return lo;
}
int main() {
vector<int> a = {1, 2, 4, 4, 4, 9};
int x = 4;
int i = first_ge(a, x);
bool ok = (i < (int)a.size() && a[i] == x);
cout << (ok ? "yes" : "no") << "\n";
return 0;
}Problem 2 — First index where a[i] ≥ X
Task: Same as lower_bound — return the leftmost insert position for x.
Idea: Identical loop to Problem 1; this is the template you reuse everywhere.
Code:
Solution 2 — code
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {1, 2, 4, 4, 4, 9};
int x = 4;
auto it = lower_bound(a.begin(), a.end(), x);
int idx = int(it - a.begin()); // first 4
cout << idx << "\n";
return 0;
}Hand-written version is the same first_ge as in Problem 1.
Problem 3 — How many times does X appear?
Task: Count occurrences of x in sorted a.
Idea: lower_bound gives the start of the run of x. upper_bound gives the first index after the run. The count is the difference.
Code:
Solution 3 — code
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {1, 2, 4, 4, 4, 9};
int x = 4;
auto L = lower_bound(a.begin(), a.end(), x);
auto R = upper_bound(a.begin(), a.end(), x);
int cnt = int(R - L);
cout << cnt << "\n"; // 3
return 0;
}Pattern summary
Reuse one “first ≥ x” search; pair with upper_bound for counts.
1i = first index with a[i] >= x // lower_bound2j = first index with a[i] > x // upper_bound3count of x = j - i
Complexity
Each call is O(log n) on a sorted array of length n.
Complexity Analysis
Time Complexity
O(log n) per query
Space Complexity
O(1) extra