Searching, sorting, recursion, and dynamic programming

01Searching

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

02Sorting

Use the standard library sort unless you are learning algorithms or have a specialized requirement. Stable sorting preserves relative order of equivalent keys; in-memory comparison sorts typically target O(n log n).

03Recursion

Recursion solves a problem by solving smaller instances of the same shape. Always identify the base case, shrinking step, and maximum depth. Deep recursion can overflow the call stack.

04Dynamic programming

Dynamic programming applies when subproblems repeat and an optimal answer can be composed from smaller answers. Memoization caches recursive results; tabulation builds results iteratively.