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