Common CP Algorithms — Binary Search & Two Pointers

Binary Search — The Idea

Given a sorted array, a linear scan checks elements one at a time — O(n) in the worst case. Binary search does better by throwing away half of the remaining search space on every comparison. It keeps two boundaries, lo and hi, checks the middle element, and then narrows the range based on whether the target is smaller or larger than that middle value.

Because the search space halves every step, binary search only needs about log₂(n) comparisons to find a target (or conclude it's absent) — for a million elements, that's around 20 comparisons instead of up to a million.

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

int binarySearch(const vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
    int target = 23;

    int idx = binarySearch(arr, target);
    if (idx != -1) cout << "Found " << target << " at index " << idx << "\n";
    else cout << target << " not found\n";

    return 0;
}

Each loop iteration eliminates roughly half of the remaining candidates, so the loop runs about log₂(n) times — that's the source of binary search's O(log n) time complexity. This only works because the array is sorted: the comparison arr[mid] < target is only meaningful if you can trust that everything to the left of mid is smaller and everything to the right is larger.

STL Binary Search: lower_bound, upper_bound, binary_search

Writing binary search by hand is a rite of passage, but <algorithm> already provides tested, general versions that work on any sorted range. std::binary_search only tells you whether a value exists; std::lower_bound and std::upper_bound tell you where — which is what you usually actually need.

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

int main() {
    vector<int> arr = {2, 5, 8, 8, 8, 12, 16, 23, 38};

    bool found = binary_search(arr.begin(), arr.end(), 8);
    cout << "Contains 8: " << (found ? "yes" : "no") << "\n";

    auto lo = lower_bound(arr.begin(), arr.end(), 8);
    auto hi = upper_bound(arr.begin(), arr.end(), 8);
    cout << "First 8 at index " << (lo - arr.begin()) << "\n";
    cout << "Count of 8s: " << (hi - lo) << "\n";

    auto pos = lower_bound(arr.begin(), arr.end(), 20);
    cout << "First element >= 20 is " << *pos << " at index " << (pos - arr.begin()) << "\n";

    return 0;
}

lower_bound(first, last, x) returns an iterator to the first element that is not less than x (i.e. the first element >= x). upper_bound(first, last, x) returns an iterator to the first element strictly greater than x. Subtracting the two — upper_bound - lower_bound — gives you the number of elements equal to x, which is a common way to count occurrences in a sorted array without scanning it. Both run in O(log n), just like manual binary search.

The Two-Pointer Technique — Pair Sum

The two-pointer technique uses two indices that move through a structure — often from opposite ends toward each other — to solve problems in a single pass instead of the O(n²) a naive nested loop would take. A classic example: given a sorted array, find a pair of elements that sum to a target value.

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

bool findPairWithSum(const vector<int>& arr, int target) {
    int left = 0, right = (int)arr.size() - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << "Pair found: " << arr[left] << " + " << arr[right] << " = " << target << "\n";
            return true;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 14, 20};
    int target = 20;

    if (!findPairWithSum(arr, target)) {
        cout << "No pair sums to " << target << "\n";
    }

    return 0;
}

Why this works: left starts at the smallest value and right at the largest. If their sum is too small, the only way to increase it is to move left forward (since the array is sorted, every element after it is at least as large). If the sum is too big, move right backward. Either way, one pointer advances every iteration, so the pointers meet after at most n steps — O(n) total, with no extra memory beyond the two indices.

Two Pointers — Removing Duplicates In-Place

Two pointers don't have to start at opposite ends — a common variant uses a slow pointer and a fast pointer moving in the same direction. This pattern shows up whenever you need to compact an array in-place, such as removing duplicates from a sorted array without allocating a second array.

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

int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < (int)arr.size(); fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1;
}

int main() {
    vector<int> arr = {1, 1, 2, 2, 2, 3, 4, 4, 5};

    int newLength = removeDuplicates(arr);
    cout << "New length: " << newLength << "\n";
    cout << "Unique elements: ";
    for (int i = 0; i < newLength; i++) cout << arr[i] << " ";
    cout << "\n";

    return 0;
}

slow marks the boundary of the unique region built so far; fast scans ahead looking for the next value different from what slow points to. Whenever it finds one, slow advances and copies that new value into place. fast visits every element exactly once, so this is also O(n) time and O(1) extra space — no new container is allocated.

Choosing the Right Tool

Both patterns need sorted (or otherwise structured) input to work correctly. Here's a quick reference for when each one is the right call: