Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 25

25日間でC言語をマスターしよう Advent Calendar 2025

@edamame2525

【C言語】探索アルゴリズム

Last updated at Posted at 2025-12-24

はじめに

この記事について

「C言語の基礎を学ぼう」をテーマに、自身の知識 + α をアドベントカレンダーにまとめます。
25日間でC言語をマスターしよう - Qiita Advent Calendar 2025 - Qiita

こんな方を対象としています

  • コンピュータがプログラムをどのように動かしているか知りたい／知らない方

  • プログラミングをしてみたい方

  • C言語初心者の方

キーワード

  • 線形探索
  • 二分探索
  • 文字列探索
  • ハッシュ

説明

探索

探索 とは複数のデータの中から一致するデータを探すことです。
基本的な探索である「線形探索」「二分探索」と「文字列探索」について説明します。

線形探索

線形探索のアルゴリズムは単純です。

  1. 配列の先頭から終端まで順番に一致するデータがあるか調べる
#include <stdio.h>

#define ARRAY_SIZE 9

int main(void) {
    int array[ARRAY_SIZE] = { 8, 3, 4, 7, 1, 6, 2, 9, 5 };
    int search_val = 1;
    int i;

    for (i = 0; i < ARRAY_SIZE; i++) {
        if (array[i] == search_val) {
            break;
        }
    }

    if (i == ARRAY_SIZE) {
        printf("見つかりませんでした。");
    } else {
        printf("%d", i);
    }

    return 0;
}

4

線形探索では配列のサイズに気を付けながら探索する必要があります。
そのデメリットを解消した線形探索に 番兵付き線形探索 というものがあります。

番兵付き線形探索のアルゴリズムは下記です。

  1. 配列の終端に探索対象のデータを付加する
  2. 線形探索を行う

番兵付き線形探索は配列のサイズを気にせず、必ず探索対象が見つかります。見つかった対象が自身が付加したものであれば、見つからなかったと解釈できます。

#include <stdio.h>

#define ARRAY_SIZE 9

int main(void) {
    int array[ARRAY_SIZE + 1] = { 8, 3, 4, 7, 1, 6, 2, 9, 5 };
    int search_val = 1;
    int i;

    array[ARRAY_SIZE] = search_val;

    for (i = 0; array[i] != search_val; i++);

    if (i == ARRAY_SIZE) {
        printf("見つかりませんでした。");
    } else {
        printf("%d", i);
    }

    return 0;
}

4

二分探索

すでにソート済みのデータから探索する場合、 二分探索 が使えます。
二分探索のアルゴリズムは下記です。

  1. 配列の中央の要素と比較する
  2. 比較結果によって、左側と右側どちらに対象データがあるかわかる
    （探索範囲が半分になる）
  3. 残りの配列の中央の要素と比較する
  4. 探索範囲が1要素になるまで繰り返す
#include <stdio.h>

#define ARRAY_SIZE 9

int main(void) {
    int array[ARRAY_SIZE] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int search_val = 4;
    int result = -1;
    int start = 0, end = ARRAY_SIZE - 1, search_index;

    while (start <= end) {
        search_index = (start + end) / 2;
        if (array[search_index] == search_val) {
            result = search_index;
            break;
        }
        if (array[search_index] < search_val) {
            start = search_index + 1;
        } else {
            end = search_index - 1;
        }
    }

    if (result == -1) {
        printf("見つかりませんでした。");
    } else {
        printf("%d", result);
    }

    return 0;
}

3

文字列探索

ある文字列 (A) の中に、ある文字列 (B) が存在するか探索する場合、線形探索のようなアルゴリズムで探索できます。
アルゴリズムは下記です。

  1. (A) を対象に (B) の1文字目が存在するか線形探索する
  2. 見つかった場合、2文字目以降もすべて一致するか確認する
  3. 一致しない場合、1文字目の線形探索を再開する
#include <stdio.h>
#include <string.h>

int main(void) {
    char array[] = "iateanappleyesterday";
    char search_str[] = "apple";
    int len_a = strlen(array); // ヌル文字を含まない長さ
    int len_s = strlen(search_str); // ヌル文字を含まない長さ
    int result = -1;
    int i, j;

    for (i = 0; i <= len_a - len_s; i++) {
        for (j = 0; j < len_s; j++) {
            if (array[i + j] != search_str[j]) {
                break;
            }
        }
        if (j == len_s) {
            // 最後までループが回った -> 見つかったということ
            result = i;
            break;
        }
    }

    if (result == -1) {
        printf("見つかりませんでした。");
    } else {
        printf("%d", result);
    }

    return 0;
}

6

ハッシュ

高速な探索アルゴリズムに ハッシュ を用いた方法があります。
任意のデータを決まった長さの短いデータに変換することを ハッシュ化 といいます。
ハッシュを利用した探索アルゴリズムはいくつかありますが、ざっくりと説明すると下記のようになります。

  1. 任意のデータを1~任意の数までのハッシュ値にハッシュ化し記憶する
    （これをハッシュテーブルといいます）
  2. 探索データをハッシュ化し、ハッシュテーブルに存在するか調べる

ハッシュの衝突がなければ、一瞬で探索することが可能です。

練習

1. 文字列のあいまい検索をしよう

任意の1文字を表す * を含んだ文字列を探索しよう。

ポイント

文字列探索のプログラムを改造します。
* がある場合の特殊処理を実装しましょう。

解答例

#include <stdio.h>
#include <string.h>

int main(void) {
    char array[] = "iateanappleyesterday";
    char search_str[] = "*ppl*";
    int len_a = strlen(array);
    int len_s = strlen(search_str); 
    int result = -1;
    int i, j;

    for (i = 0; i <= len_a - len_s; i++) {
        for (j = 0; j < len_s; j++) {
            if (search_str[j] != '*' && array[i + j] != search_str[j]) { // 追加
                break;
            }
        }
        if (j == len_s) {
            result = i;
            break;
        }
    }

    if (result == -1) {
        printf("見つかりませんでした。");
    } else {
        printf("%d", result);
    }

    return 0;
}

6

2. 線形探索 vs 二分探索

線形探索と二分探索の実行速度を比較しよう。

ポイント

線形探索の速度とソートと二分探索の速度をそれぞれ計測します。

解答例

ソートは前日のクイックソートを使用しました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 20000000

void quick_sort(int *array, int start, int end);
void swap(int *array, int el_num1, int el_num2);
int linear_search(int *array, int size, int search_val);
int binary_search(int *array, int size, int search_val);
void print_time(clock_t start, clock_t end);

int main(void) {
    int search_val;
    int i;
    clock_t start_time, end_time;

    // スタックオーバーフロー対策
    // ヒープ領域にメモリを確保する
    int *array1 = (int *)malloc(sizeof(int) * ARRAY_SIZE);
    int *array2 = (int *)malloc(sizeof(int) * ARRAY_SIZE);

    srand((unsigned int)time(NULL));

    for (i = 0; i < ARRAY_SIZE; i++) {
        array1[i] = array2[i] = rand() % ARRAY_SIZE;
    }
    search_val = -1; // 最後まで探索してもらうために-1を設定

    // 線形探索
    start_time = clock();
    printf("%d\n", linear_search(array1, ARRAY_SIZE, search_val));
    end_time = clock();
    print_time(start_time, end_time);
    printf("\n");

    // ソートしてから
    start_time = clock();
    quick_sort(array2, 0, ARRAY_SIZE - 1);
    end_time = clock();
    print_time(start_time, end_time);
    // 二分探索
    start_time = clock();
    printf("%d\n", binary_search(array2, ARRAY_SIZE, search_val));
    end_time = clock();
    print_time(start_time, end_time);

    free(array1);
    free(array2);

    return 0;
}

void quick_sort(int *array, int start, int end) {
    if (start >= end) return;

    int pivot = array[end];

    int left = start;
    int target;
    for (target = left; target <= end; target++) {
        if (array[target] < pivot) {
            swap(array, left, target);
            left++;
        }
    }
    swap(array, left, end);

    quick_sort(array, start, left - 1);
    quick_sort(array, left + 1, end);
}

void swap(int *array, int el_num1, int el_num2) {
    int temp = array[el_num1];
    array[el_num1] = array[el_num2];
    array[el_num2] = temp;
}

void print_time(clock_t start, clock_t end) {
    printf("実行時間: %f 秒\n", ((double)(end - start)) / CLOCKS_PER_SEC);
}

int linear_search(int *array, int size, int search_val) {
    int i;
    for (i = 0; i < size; i++) {
        if (array[i] == search_val) {
            return i;
        }
    }
    return -1;
}

int binary_search(int *array, int size, int search_val) {
    int start = 0, end = size - 1, search_index;
    while (start <= end) {
        search_index = (start + end) / 2;
        if (array[search_index] == search_val) {
            return search_index;
        }
        if (array[search_index] < search_val) {
            start = search_index + 1;
        } else {
            end = search_index - 1;
        }
    }
    return -1;
}

-1
実行時間: 0.011000 秒

実行時間: 5.019000 秒
-1
実行時間: 0.000000 秒

C言語、高速ですね。
二分探索のほうが高速ですが、線形探索も十分高速でした。
（連続したメモリ領域だからなのでしょうか...？）
何度も検索するような場面では、あらかじめソートしておいて二分探索を選択したいですね。

おわりに

アルゴリズムの特性を理解し、その実行時間を知っておくことで品質が良いプログラムが作れそうです。

そして...！この記事で「25日間でC言語をマスターしよう」アドベントカレンダーは終わりです！ありがとうございました！
いつかのどなたかのC言語勉強のきっかけになれば嬉しいです♪

参考文献

↓↓↓ はじめてプログラミングを学んだときに読んだ本です ↓↓↓
詳細（プログラミング入門　C言語）｜プログラミング｜情報｜実教出版

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?