Algorithme de recherche et exemples d'application en C++

Algorithmes de recherche et exemples d'application en C++

En C++, un algorithme de recherche fait référence à un algorithme qui trouve des éléments spécifiques dans un ensemble de données. Il s’agit de l’un des algorithmes les plus fondamentaux et les plus couramment utilisés dans les programmes informatiques et il est largement utilisé dans divers problèmes pratiques. Cet article présentera plusieurs algorithmes de recherche couramment utilisés en C++ et donnera des exemples d'application correspondants pour aider les lecteurs à mieux comprendre et maîtriser ces algorithmes.

1. Algorithme de recherche linéaire

L'algorithme de recherche linéaire (également appelé algorithme de recherche séquentielle) est l'algorithme de recherche le plus simple et le plus basique. Son idée de base est de comparer un par un en partant du premier élément des données jusqu'à trouver l'élément cible. Voici le code pour implémenter la recherche linéaire en C++ :

int linearSearch(int arr[], int n, int x)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            return i;   // 找到目标元素返回其下标
        }
    }
    return -1;  // 未找到目标元素返回 -1
}

La complexité temporelle de l'algorithme de recherche linéaire est O(n), où n représente la taille des données, c'est-à-dire le nombre d'éléments dans les données. Si l'élément à trouver se trouve à la dernière position dans les données, alors la recherche linéaire doit parcourir l'intégralité des données pour trouver l'élément cible, et la complexité temporelle atteindra O(n) dans le pire des cas. Par conséquent, les algorithmes de recherche linéaire ne sont pas efficaces lorsque la taille des données est importante.

2. Algorithme de recherche binaire

L'algorithme de recherche binaire (également appelé algorithme de demi-recherche) est un algorithme de recherche efficace. Cela nécessite que les données soient en ordre, et réduit la portée de la recherche de moitié à chaque recherche, et trouve enfin l'élément cible. Voici le code pour implémenter la recherche binaire en C++ :

int binarySearch(int arr[], int n, int x)
{
    int left = 0, right = n - 1, mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] == x)
        {
            return mid;   // 找到目标元素返回其下标
        }
        else if (arr[mid] > x)
        {
            right = mid - 1;   // 目标元素在左边区域
        }
        else
        {
            left = mid + 1;   // 目标元素在右边区域
        }
    }
    return -1;  // 未找到目标元素返回 -1
}

La complexité temporelle de l'algorithme de recherche binaire est O(log n), où n représente la taille des données, c'est-à-dire le nombre d'éléments dans les données. L'algorithme de recherche binaire tire parti des caractéristiques des données ordonnées. Chaque recherche peut réduire de moitié la plage de recherche pour trouver rapidement l'élément cible. Cependant, lorsque les données ne sont pas triées, elles doivent être triées avant que la recherche binaire puisse être utilisée, ce qui ajoutera une complexité temporelle supplémentaire.

3. Algorithme de recherche de hachage

L'algorithme de recherche de hachage (également appelé algorithme de recherche de hachage) est un algorithme qui utilise des fonctions de hachage pour effectuer une recherche rapide. Il trouve rapidement l'élément cible en mappant l'élément de données à une position fixe (c'est-à-dire une valeur de hachage). Voici le code pour implémenter la recherche de hachage en C++ :

const int MAX_SIZE = 10007;   // 哈希表的最大长度

struct Node
{
    int key, value;   // 哈希表中存放的元素
    Node* next;   // 指向下一个节点的指针
};

class HashTable
{
private:
    Node* table[MAX_SIZE];   // 哈希表的数组
    int hashFunc(int key) { return key % MAX_SIZE; }   // 哈希函数

public:
    HashTable() { memset(table, 0, sizeof(table)); }   // 初始化哈希表

    void insert(int key, int value)   // 将元素插入哈希表
    {
        int pos = hashFunc(key);
        Node* p = new Node();
        p->key = key;
        p->value = value;
        p->next = table[pos];
        table[pos] = p;
    }

    int search(int key)   // 在哈希表中查找元素
    {
        int pos = hashFunc(key);
        Node* p = table[pos];
        while (p != NULL)
        {
            if (p->key == key)
            {
                return p->value;   // 找到目标元素返回其值
            }
            p = p->next;
        }
        return -1;  // 未找到目标元素返回 -1
    }
};

La complexité temporelle de l'algorithme de recherche de hachage est O(1), qui n'est pas affectée par la taille des données et est très efficace. Cependant, de nombreux facteurs doivent être pris en compte lors de la conception de la fonction de hachage. Si la fonction de hachage n'est pas bonne, cela peut provoquer des conflits de hachage, affectant ainsi l'efficacité de la recherche.

4. Exemples d'application d'algorithmes de recherche

En plus des trois algorithmes de recherche ci-dessus, il existe de nombreux autres algorithmes de recherche en C++, tels que la recherche par interpolation, la recherche de Fibonacci, etc. Un exemple d'application simple est donné ci-dessous pour montrer l'application de l'algorithme de recherche à des problèmes pratiques.

Étant donné un tableau et une valeur cible, trouvez la somme de deux nombres dans le tableau égale à la valeur cible et renvoyez les indices des deux nombres. Voici le code pour implémenter cette fonction en C++ :

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> umap;
    int size = nums.size();
    for (int i = 0; i < size; i++)
    {
        int complement = target - nums[i];
        if (umap.find(complement) != umap.end())
        {
            return { umap[complement], i };
        }
        umap[nums[i]] = i;
    }
    return {};
}

Cet algorithme utilise l'idée de recherche de hachage Pendant le processus de parcours du tableau, il recherche dans la table de hachage s'il y a un élément qui s'ajoute au courant. élément à la valeur cible. If Renvoie leurs indices s'ils existent.

Résumé

Cet article présente trois algorithmes de recherche couramment utilisés en C++ : l'algorithme de recherche linéaire, l'algorithme de recherche binaire et l'algorithme de recherche de hachage, et donne des exemples d'application correspondants. Comprendre les avantages, les inconvénients et les applications pratiques de ces algorithmes de recherche peut nous aider à mieux les utiliser en programmation et à améliorer l'efficacité et la qualité du programme.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!