C++での検索アルゴリズムと応用例

C における検索アルゴリズムとアプリケーションの例

C では、検索アルゴリズムとは、データ セット内の特定の要素を見つけるためのアルゴリズムを指します。これは、コンピューター プログラムで最も基本的で一般的に使用されるアルゴリズムの 1 つであり、さまざまな実際の問題で広く使用されています。この記事では、C で一般的に使用されるいくつかの検索アルゴリズムを紹介し、読者がこれらのアルゴリズムをよりよく理解して習得できるように、対応するアプリケーション例を示します。

1. 線形探索アルゴリズム

線形探索アルゴリズム (逐次探索アルゴリズムとも呼ばれる) は、最も単純かつ基本的な探索アルゴリズムです。その基本的な考え方は、データの最初の要素から始めて、目的の要素が見つかるまで 1 つずつ比較することです。以下は、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
}

線形検索アルゴリズムの時間計算量は O(n) です。ここで、n はデータのサイズ、つまりデータの要素数を表します。データ。検索対象の要素がデータ内の最後の位置にある場合、線形検索はターゲット要素を見つけるためにデータ全体を横断する必要があり、時間計算量は最悪の場合 O(n) に達します。したがって、データ サイズが大きい場合、線形探索アルゴリズムは効率的ではありません。

2. 二分探索アルゴリズム

二分探索アルゴリズム (二分探索アルゴリズムとも呼ばれる) は、効率的な検索アルゴリズムです。データが順序どおりである必要があり、検索ごとに検索範囲を半分に減らし、最終的にターゲット要素を見つけます。以下は、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
}

バイナリ検索アルゴリズムの時間計算量は O(log n) です。ここで、n はデータのサイズ、つまり要素の数を表します。データの中で。二分探索アルゴリズムは、順序付けされたデータの特性を利用し、1回の探索で探索範囲を半分にすることができ、目的の要素を素早く見つけることができます。ただし、データが並べ替えられていない場合は、二分検索を使用する前に並べ替える必要があるため、時間の複雑さがさらに増大します。

3. ハッシュ検索アルゴリズム

ハッシュ検索アルゴリズム (ハッシュ検索アルゴリズムとも呼ばれます) は、ハッシュ関数を使用して高速に検索するアルゴリズムです。データ要素を固定位置 (つまりハッシュ値) にマッピングすることで、ターゲット要素をすばやく見つけます。以下は、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
    }
};

ハッシュ検索アルゴリズムの時間計算量は O(1) で、データのサイズに影響されず、非常に効率的です。ただし、ハッシュ関数の設計には多くの考慮すべき要素があり、ハッシュ関数が適切でない場合、ハッシュの競合が発生し、検索効率に影響を与える可能性があります。

4. 検索アルゴリズムの適用例

上記の 3 つの検索アルゴリズム以外にも、内挿検索、フィボナッチ検索など、C には多数の検索アルゴリズムがあります。実際の問題における検索アルゴリズムの応用を示すために、簡単な応用例を以下に示します。

配列とターゲット値が与えられた場合、ターゲット値に等しい配列内の 2 つの数値の合計を見つけ、2 つの数値の添え字を返します。この関数を 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 {};
}

このアルゴリズムはハッシュ検索の考え方を使用しており、配列を走査するプロセス中に、ハッシュ テーブル内でターゲット値があるかどうかを検索します。現在の要素に追加され、存在する場合はそのインデックスを返します。

概要

この記事では、C で一般的に使用される 3 つの検索アルゴリズム (線形検索アルゴリズム、二分検索アルゴリズム、ハッシュ検索アルゴリズム) を紹介し、対応するアプリケーション例を示します。これらの検索アルゴリズムの長所、短所、および実際の応用を理解することは、プログラミングでアルゴリズムをより適切に使用し、プログラムの効率と品質を向上させるのに役立ちます。

以上がC++での検索アルゴリズムと応用例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。