Algorithms in C++

From storing data to using it

In Data Structures in C++, you practiced choosing containers like vector, stacks, queues, maps, and tree-shaped data.

Now we ask the next question:

Once the data is stored, what do we do with it efficiently?

Algorithms are repeatable procedures for tasks like:

• finding a value
• sorting records
• filtering important items
• counting patterns
• deciding whether something exists

If data structures are the nouns of programming, algorithms are the verbs. In AI, finance, web backends, games, and systems programming, performance often comes from pairing the right container with the right algorithm.

A recipe with constraints

An algorithm is not just “some code that works.” It is a clear procedure with tradeoffs.

When you design or choose an algorithm, ask:

1. Input: What data do I start with?
2. Output: What result do I need?
3. Correctness: Does it always produce the right answer?
4. Efficiency: How much time and memory does it use?

For example, if you have stock prices in a vector<double> and need the first price above a threshold, you could scan from left to right. That is simple, correct, and often good enough.

But if you need to search millions of times per second, the algorithm choice matters a lot.

The simplest useful search

A linear search checks items one by one until it finds what it needs.

This works on an unsorted vector, which makes it flexible. The tradeoff is that in the worst case, you may inspect every element.

In Big-O notation, linear search is O(n), where n is the number of items.

That means if the input doubles, the worst-case work roughly doubles too.

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

int firstPriceAbove(const vector<double>& prices, double threshold) {
    for (int i = 0; i < prices.size(); i++) {
        if (prices[i] > threshold) {
            return i;
        }
    }
    return -1;
}

int main() {
    vector<double> prices = {101.5, 99.2, 103.8, 108.1, 104.0};
    double threshold = 105.0;

    int index = firstPriceAbove(prices, threshold);

    if (index != -1) {
        cout << "First price above " << threshold << " is "
             << prices[index] << " at index " << index << endl;
    } else {
        cout << "No price was above " << threshold << endl;
    }

    return 0;
}
```

You have an unsorted vector<int> containing user IDs. You need to determine whether a particular ID appears in the vector once.

Which approach is the most direct fit?

Sorting unlocks faster search

If your data is sorted, you can use binary search.

Binary search repeatedly cuts the search space in half:

[ 2  5  8  12  16  23  38 ]
          ^ check middle

Instead of checking every item, binary search discards half the remaining possibilities each step.

• Sorting with std::sort: usually O(n log n)
• Binary search with std::binary_search: O(log n)

This tradeoff is common in backend systems and finance: pay an upfront sorting cost, then perform many fast lookups.

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

int main() {
    vector<int> responseTimes = {42, 18, 75, 30, 18, 91, 60};

    sort(responseTimes.begin(), responseTimes.end());

    cout << "Sorted response times: ";
    for (int time : responseTimes) {
        cout << time << " ";
    }
    cout << endl;

    int target = 75;
    bool found = binary_search(responseTimes.begin(), responseTimes.end(), target);

    cout << "Was " << target << " found? ";
    cout << (found ? "yes" : "no") << endl;

    return 0;
}
```

True or false?

Binary search is only reliable when the range being searched is sorted according to the same ordering used by the search.

Prefer tested building blocks

C++ includes many algorithms in the Standard Library, especially through the <algorithm> header.

You have already used containers. Now you can combine them with reusable algorithms:

• sort arranges a range
• binary_search checks whether a sorted range contains a value
• count_if counts items matching a condition
• min_element finds the smallest item
• max_element finds the largest item

These algorithms usually work with iterators, such as v.begin() and v.end(), which describe the range to process.

The result is code that is shorter, more reliable, and easier to reason about.

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

class Transaction {
public:
    string symbol;
    double amount;

    Transaction(string s, double a) : symbol(s), amount(a) {}
};

int main() {
    vector<Transaction> trades = {
        Transaction("AAPL", 1200.50),
        Transaction("MSFT", 850.00),
        Transaction("NVDA", 2500.75),
        Transaction("TSLA", 400.25)
    };

    int largeTrades = count_if(trades.begin(), trades.end(), [](const Transaction& t) {
        return t.amount >= 1000.0;
    });

    auto smallest = min_element(trades.begin(), trades.end(), [](const Transaction& a, const Transaction& b) {
        return a.amount < b.amount;
    });

    cout << "Large trades: " << largeTrades << endl;
    cout << "Smallest trade: " << smallest->symbol << " $" << smallest->amount << endl;

    return 0;
}
```

Fill in the blank.

The STL algorithm that rearranges a range into sorted order is called std::____.

Match the algorithm to the situation

There is rarely one “best” algorithm in isolation. The best choice depends on the data and the job.

Use this mental checklist:

Situation Good first thought Data is unsorted and you search once Linear search Data is sorted and you search often Binary search You need ordered output std::sort You need to count matching items std::count_if You need smallest/largest item std::min_element / std::max_element

Also consider whether modifying the data is okay. sort changes the order of the container, which may be exactly what you want—or a bug if the original order matters.

This is where earlier lessons connect: C++ syntax lets you express the steps, objects can model real entities, containers hold the data, and algorithms turn that data into answers.

What you can now do

You have moved from storing data to operating on it effectively.

Key ideas from this lesson:

• Algorithms are repeatable procedures for transforming or querying data.
• Linear search is simple and works on unsorted data.
• Sorting can enable faster repeated searches.
• STL algorithms help you write concise, tested C++.
• Efficiency matters, especially as input size grows.

In the next lesson, File Handling in C++, you will see how programs can read and write data outside the running program—then these same containers and algorithms become useful on real stored information.