Algorithmes de recherche en C++ : guide détaillé

What is it and why? (a real-life analogy)

Imagine you are standing in front of a huge bookshelf in a library, on which 10,000 books are arranged in strict alphabetical order. You need to find the book "Programming in C++ for Beginners". How would you proceed?

The first way (naive): You start looking through the books one by one, starting from the first shelf. You look at the spine, read the title, move on to the next one. Sooner or later you will find the right book, but it could take several hours. This is linear search.

The second way (smart): You open the catalog, see that the book is in the "Programming Languages" section, the "C++" subsection, on shelf #7. You immediately go to the right shelf and find the book in 2 minutes. This is index search (like in databases).

The third way (brilliant): You know the books are in alphabetical order. You open a book roughly in the middle of the shelf. You see it's the letter "M". Your book starts with "P" — it's to the right. You discard the left half and repeat the process with the right half. Divide in half again, discard the unnecessary part again. In just 14 steps (because 2¹⁴ ≈ 16,000) you are guaranteed to find any book. This is binary search.

💡 Important: Search algorithms are not just "find an element in an array". They are the foundation upon which databases, search engines (Google), antiviruses, games, and even artificial intelligence are built. If you learn to understand search, you will understand how half of all computer science works.

In programming, we are constantly searching: for a user in a database, a word in text, a file in a folder, the shortest path on a map. Without efficient search algorithms, the modern world would simply stop — your browser would take hours to load a page instead of seconds.

Theory: how it works from the inside

Let's figure out what happens "under the hood" of a computer when we run a search. This is not magic, but strict mathematical logic.

1. Linear Search

Essence: We go through each element of the array from beginning to end and compare it with the target value. As soon as we find it, we return the index. If we reach the end and don't find it, we return -1 (or another "not found" signal).

Complexity: O(n) — in the worst case (when the element is not present) we will check all n elements. In the best case (the element is first) — O(1).

When to use: When the array is small (up to 100 elements) or when the array is not sorted. This is the only universal search.

2. Binary Search

Essence: Works ONLY on sorted data. We look at the middle of the array. If the target value is less than the middle, we search in the left half. If greater, in the right half. We repeat until we find it or until the boundaries converge.

Complexity: O(log n) — logarithmic. For an array of 1,000,000 elements, only 20 comparisons are needed (because 2²⁰ ≈ 1,000,000).

Important condition: The array must be sorted in ascending (or descending) order. If the data is not sorted, binary search will produce garbage.

3. Depth-First and Breadth-First Search (for graphs)

This is already an advanced topic, but it's worth mentioning. If we have a graph (e.g., a subway map or a social network), we can search:

• DFS (Depth-First Search) — go to the end of one branch, then come back and go along another. Like a cave explorer: you go to the farthest hall, then return to the fork.
• BFS (Breadth-First Search) — go to all neighbors, then to the neighbors of neighbors. Like a wave from a thrown stone: first a circle, then wider.

4. Hash Search

The fastest search — O(1) on average. We use a hash table (unordered_map in C++). Each key corresponds to a unique address (hash). We immediately know where the value is, without iterating. Like a cloakroom attendant who remembers which hanger your coat is on because you have a ticket.

Syntax in C++: all forms and variants

In C++, there are several ways to implement search. Let's look at each one.

1. Manual implementation (for understanding)

You write the loop yourself. This is the best way to understand how the algorithm works.

2. Standard Library (STL)

C++ provides ready-made functions. You need to know them and use them in real projects.

3. Search in containers

Different containers