C言語

【C言語】第8章第3回:検索アルゴリズム:線形探索と二分探索

検索アルゴリズムは、データから特定の値を効率的に見つける技術です。本記事では、線形探索と二分探索の仕組みと実装方法を学びます。

0. 記事の概要

この記事を読むメリット

  • 検索スキルを向上:データを効率的に探索する方法を理解できます。
  • プログラムの効率化:データ処理を最適化するための基礎が身につきます。
  • 応用力の強化:データ検索に基づいた高度なアルゴリズムの理解が深まります。

この記事で学べること

  • 線形探索の仕組みと実装方法
  • 二分探索の仕組みと実装方法
  • 効率性の比較と適切な場面での使い分け

活用のイメージ

検索アルゴリズムは、データベース、検索エンジン、ファイル管理などの分野で幅広く応用されています。

1. 線形探索

1.1 線形探索とは?

線形探索(Linear Search)は、データセットの最初から最後まで1つずつ順番に調べて目標値を探すアルゴリズムです。

例:

データセット:[5, 3, 8, 1, 2]

目標値:8

結果:4回目の比較で見つかる。

1.2 線形探索の実装

#include <stdio.h>

int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // 見つかった場合、インデックスを返す
        }
    }
    return -1; // 見つからなかった場合
}

int main() {
    int arr[] = {5, 3, 8, 1, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 8;

    int result = linearSearch(arr, size, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}
動作解説
  1. 配列とターゲットを定義:検索対象のデータセットを用意します。
  2. 順番に比較:linearSearch()関数がデータセットを1つずつ比較します。
  3. 結果を出力:目標値が見つかった場合、そのインデックスを表示します。

2. 二分探索

2.1 二分探索とは?

二分探索(Binary Search)は、ソートされたデータセットを対象に、データを半分に分割しながら目標値を探す効率的なアルゴリズムです。

例:

データセット:[1, 2, 3, 4, 5]

目標値:4

結果:2回目の比較で見つかる。

2.2 二分探索の実装

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid; // 見つかった場合、インデックスを返す
        } else if (arr[mid] < target) {
            left = mid + 1; // 右側を探索
        } else {
            right = mid - 1; // 左側を探索
        }
    }
    return -1; // 見つからなかった場合
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 4;

    int result = binarySearch(arr, size, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}
動作解説
  1. 配列の定義:ソートされたデータセットを用意します。
  2. 比較と分割:中央値を計算し、目標値と比較して探索範囲を絞り込みます。
  3. 結果を出力:目標値が見つかった場合、そのインデックスを表示します。

3. 練習問題

以下の課題に挑戦して、検索アルゴリズムの理解を深めましょう。

  1. 二分探索を改良して、再帰的に実装してください。
  2. 線形探索を改良して、最初に見つかった位置だけでなく、全ての一致する位置を表示するプログラムを作成してください。
  3. 二分探索での探索回数をカウントし、表示する機能を追加してください。

4. 練習問題の解答と解説

問1の解答

#include <stdio.h>

int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, right, target);
    } else {
        return binarySearchRecursive(arr, left, mid - 1, target);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 4;

    int result = binarySearchRecursive(arr, 0, size - 1, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }

    return 0;
}

このプログラムでは、二分探索を再帰的に実装し、目標値を効率的に探します。

5. まとめ

本記事では、基本的な検索アルゴリズムである線形探索と二分探索の仕組みと実装方法を学びました。次回は、スタックとキューの基本と応用について解説します。