The naive approach and its limits
The most straightforward way to find a value x in an array is a simple for loop:
for (int i = 0; i < n; i++) {
if (array[i] == x) {
// x found at index i
}
}
This works perfectly — but its time complexity is O(n). In the worst case you inspect every element. For arbitrary (unsorted) arrays, this is actually optimal; you have no information about where x might be.
When does this become a problem? With n = 106 and 105 queries, you're doing 1011 operations — about 100× over a typical time limit.
But if the array is sorted, the situation changes entirely. Order carries information. Binary search exploits that information to find any element in O(log n) time.
Method 1 — classic halving
Think of how you look up a word in a dictionary. You open roughly to the middle, check whether the word comes before or after, then repeat on the relevant half. This is exactly what Method 1 implements.
The algorithm maintains an active region [a, b] in the array. At each step it checks the middle element and halves the region, until either the element is found or the region collapses.
int a = 0, b = n-1;
while (a <= b) {
int k = (a+b)/2;
if (array[k] == x) {
// x found at index k
}
if (array[k] > x) b = k-1;
else a = k+1;
}
The active region starts at size n and halves each iteration, giving at most ⌈log₂ n⌉ iterations — hence O(log n).
Method 2 — jump search variant
An alternative that's elegant to reason about: instead of tracking a region, track a jump length and walk forward.
int k = 0;
for (int b = n/2; b >= 1; b /= 2) {
while (k+b < n && array[k+b] <= x) k += b;
}
if (array[k] == x) {
// x found at index k
}
The outer loop runs ⌈log₂ n⌉ times and the inner while executes at most twice per jump length — so the total is still** O(log n)**
C++ STL functions
lower_bound Pointer to first element ≥ x
upper_bound Pointer to first element > x
equal_range Both pointers as a pair
If no such element exists, all three point one past the last element. Here's how to check for x:
auto k = lower_bound(array, array+n, x) - array;
if (k < n && array[k] == x) {
// x found at index k
}
Counting how many times x appears:
auto a = lower_bound(array, array+n, x);
auto b = upper_bound(array, array+n, x);
cout << b-a << "\n";
Using equal_range for the same result in one call:
auto r = equal_range(array, array+n, x);
cout << r.second - r.first << "\n";
In contests, prefer the STL functions whenever you just need a boundary — they're battle-tested and save debugging time. Write Method 1 or 2 explicitly when the predicate is non-standard (e.g. searching on a function's output rather than an array).
