Sorting with Custom Logic

The standard library function std::sort is a highly efficient tool for ordering data, typically implementing a variation of quicksort with a time complexity of O(n log n). While it is defined in the <algorithm> header, it is commonly accessed via <bits/stdc++.h> in competitive programming environments.

Basic Usage and Custom Comparators

The function signature is sort(start, end, comparator). The start iterator points to the first element, and end points to one past the last element. If no comparator is provided, the container sorts in ascending order.

To handle complex sorting requirements, such as ordering struct fields or applying mathematical transformations, you must define a custom comparater function. This function returns true if the first argument should appear before the second.

Consider a scenario where we want to sort integers based on the value of their last digit (units place) in descending order:

bool customRule(int a, int b) {
    return (a % 10) > (b % 10);
}

Implementing this in a full program:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool customRule(int a, int b) {
    return (a % 10) > (b % 10);
}

int main() {
    vector<int> data = {65, 59, 96, 13, 21, 80, 72, 33, 44, 99};
    
    sort(data.begin(), data.end(), customRule);
    
    for(int val : data) {
        cout << val << " ";
    }
    // Output: 59 99 96 65 44 13 33 72 21 80
    return 0;
}

Binary Search Techniques

Binary search is a fundamental algorithm used to find a target value or a boundary within a sorted range by repeatedly dividing the search interval in half. While often associated with sorted arrays, the concept extends to finding a "critical point" where a property changes from true to false.

Implementation Templates

There are two primary templates for binary search depending on how you partition the interval [left, right].

Template 1: Finding the first occurrence / lower bound
This divides the range into [L, mid] and [mid+1, R].

while (left < right) {
    int mid = left + ((right - left) >> 1); // Avoids overflow
    if (check(mid)) {
        right = mid; // Keep mid, search left
    } else {
        left = mid + 1; // mid is not valid, search right
    }
}

Template 2: Finding the last occurrence / upper bound
This divides the range into [L, mid-1] and [mid, R]. Note the addition of 1 to the midpoint calculation to prevent an infinite loop.

while (left < right) {
    int mid = left + ((right - left + 1) >> 1); // Bias towards right
    if (check(mid)) {
        left = mid; // Keep mid, search right
    } else {
        right = mid - 1; // mid is not valid, search left
    }
}

Binary Search on Answers

Beyond searching indexes, binary search is powerful for optimization problems (Binary Search on Answers). If the potential answers fall within a known range and satisfy a monotonic porperty (if a value x works, all values less than x work, or vice versa), you can binary search the answer space. Common patterns include:

• Minimizing the maximum value (Minimax).
• Maximizing the minimum value (Maximin).
• Finding the boundary of feasibility.

Greedy Algorithms

Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit (local optimum) without worying about the global picture. For a greedy approach to be correct, the problem must exhibit "optimal substructure" and the choice must be "safe" (not affecting future choices negatively).

General Workflow

1. Identify the optimal substructure of the problem.
2. Break the problem down into a sequence of steps.
3. At each step, make the choice that looks best right now.
4. Combine these local choices to form the final solution.

The main advantage of greedy methods is efficiency. By making a decision at each step and moving forward, you avoid the expensive recursion or dynamic programming states required for global optimization.