読み込み中...

C++で二分探索をマスターする7つの方法

C++で二分探索を学ぶイメージ C++
2024.03.18
この記事は約24分で読めます。

【サイト内のコードはご自由に個人利用・商用利用いただけます】

この記事では、プログラムの基礎知識を前提に話を進めています。

説明のためのコードや、サンプルコードもありますので、もちろん初心者でも理解できるように表現してあります。

本記事のサンプルコードを活用して機能追加、目的を達成できるように作ってありますので、是非ご活用ください。

※この記事は、一般的にプロフェッショナルの指標とされる『実務経験10,000時間以上』を満たす現役のプログラマチームによって監修されています。

※Japanシーモアは、常に解説内容のわかりやすさや記事の品質に注力しております。不具合、分かりにくい説明や不適切な表現、動かないコードなど気になることがございましたら、記事の品質向上の為にお問い合わせフォームにてご共有いただけますと幸いです。
(送信された情報は、プライバシーポリシーのもと、厳正に取扱い、処分させていただきます。)

はじめに

C++で二分探索を学ぶことは、プログラミングスキルを高める上で非常に重要です。

この記事では、C++における二分探索の基礎から応用までを徹底的に解説します。

プログラミング初心者から上級者まで、C++での二分探索をマスターするために必要なすべてを学べる内容となっています。

初めてC++を学ぶ方でも理解しやすいように、基本的な概念から順を追って説明していきます。

これを読めば、C++における二分探索の知識を深め、実践的なスキルを身につけることができるでしょう。

●C++とは

C++は、汎用プログラミング言語の一つで、高いパフォーマンスと効率的なメモリ管理が特徴です。

C言語をベースにオブジェクト指向の概念が追加されています。

C++は、システムプログラミングやアプリケーション開発、ゲーム開発など幅広い分野で使用されています。

また、ポインタや参照、クラス、テンプレートなど、独自の機能を多数持っています。

この言語の特徴を理解することで、より効果的なプログラミングが可能になります。

○C++の基本構造と特徴

C++の基本構造は、関数、クラス、オブジェクトなどから成り立っています。

最も基本的な構成要素は関数であり、特に「main」関数はプログラムの実行開始点です。

C++では、データをカプセル化し、オブジェクト指向の原則に基づいてクラスを定義します。

これにより、再利用可能で保守しやすいコードを作成することができます。

また、C++は強力な型チェックを提供し、エラーの可能性を低減します。

さらに、テンプレートを使用することで、型に依存しない汎用的な関数やクラスを作成できるのも大きな特徴です。

これらの特徴を把握し、C++の強力な機能を活用することで、効率的かつ効果的なプログラミングが可能となります。

●二分探索の基本

二分探索は、効率的な検索アルゴリズムの一つです。

このアルゴリズムは、ソート済みの配列やリストにおいて、特定の要素を高速に検索するために用いられます。

二分探索の基本的な考え方は、データの中間点を選び、探している値と比較することによって、検索範囲を半分に絞り込むというものです。

このプロセスを目的の値が見つかるか、検索範囲がなくなるまで繰り返します。

二分探索は、線形探索よりもはるかに高速であり、大量のデータを扱う場合に特に有効です。

○二分探索とは何か

二分探索は、中央値を基にした探索方法です。

探索対象の配列やリストがソートされている必要があります。

探索開始時には、最小インデックスと最大インデックスを使用して検索範囲を定義します。

その後、範囲の中間点の値を検索対象の値と比較し、もし中間点の値が探索値より大きければ、検索範囲を中間点より下の範囲に絞り込みます。

逆に、中間点の値が探索値より小さければ、検索範囲を中間点より上の範囲に絞り込みます。

このプロセスを繰り返すことで、目的の値を効率的に見つけ出すことができます。

○二分探索のアルゴリズム理解

二分探索アルゴリズムを理解するためには、そのステップを詳細に追うことが重要です。

まず、ソートされた配列を用意し、検索対象の値を定めます。

次に、配列の最小インデックスと最大インデックスを定義し、これらを用いて中間インデックスを計算します。

中間インデックスの値を検索対象の値と比較し、もし等しければ、その値が見つかったことになります。

等しくない場合は、比較結果に基づいて検索範囲を半分に絞り込みます。

このプロセスを検索値が見つかるか、あるいは検索範囲が存在しなくなるまで繰り返します。

二分探索は計算量が対数時間であるため、非常に効率的な探索方法とされています。

●二分探索のC++における実装

C++での二分探索の実装は、プログラマーが理解すべき重要なスキルの一つです。

二分探索アルゴリズムは、効率的なデータ検索に役立ち、特に大きなデータセットでその性能を発揮します。

C++における二分探索の実装には、いくつかの重要な要素が関与します。

まず、配列またはコンテナがソートされている必要があります。

次に、検索対象の値を特定し、その値を配列の中間値と比較しながら探索範囲を狭めていきます。

このプロセスは、目的の値が見つかるか、探索範囲が存在しなくなるまで繰り返されます。

○サンプルコード1：基本的な二分探索

C++での基本的な二分探索の実装例を紹介します。

このサンプルコードでは、ソートされた整数配列内で指定された値を探索します。

関数は、見つかった要素のインデックス、または見つからなかった場合は-1を返します。

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid; // 見つかった場合、インデックスを返す
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1; // 見つからなかった場合、-1を返す
}

int main() {
    std::vector<int> data = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 11;
    int result = binarySearch(data, target);
    if (result != -1) {
        std::cout << "要素はインデックス " << result << " にあります。\n";
    } else {
        std::cout << "要素は配列内に存在しません。\n";
    }
    return 0;
}

このコードでは、binarySearch関数が二分探索の核心部分を担っています。

配列と検索対象の値を受け取り、中間値を基に検索を行い、結果を返します。

○サンプルコード2：再帰による二分探索

二分探索は、再帰的なアプローチを用いても実装できます。

再帰による二分探索では、関数が自身を呼び出し、検索範囲を狭めていきます。

下記のサンプルコードは、再帰を使用した二分探索の例です。

#include <iostream>
#include <vector>

int binarySearchRecursive(const std::vector<int>& arr, int low, int high, int target) {
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid; // 見つかった場合、インデックスを返す
        } else if (arr[mid] > target) {
            return binarySearchRecursive(arr, low, mid - 1, target);
        } else {
            return binarySearchRecursive(arr, mid + 1, high, target);
        }
    }
    return -1; // 見つからなかった場合、-1を返す
}

int main() {
    std::vector<int> data = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int target = 10;
    int result = binarySearchRecursive(data, 0, data.size() - 1, target);
    if (result != -1) {
        std::cout << "要素はインデックス " << result << " にあります。\n";
    } else {
        std::cout << "要素は配列内に存在しません。\n";
    }
    return 0;
}

このコードでは、binarySearchRecursive関数が再帰的に自身を呼び出し、中間値を更新しながら検索を行います。

○サンプルコード3：二分探索のエラー処理

二分探索の実装において、エラー処理は重要な側面です。

特に、無効な入力や検索対象が配列に存在しない場合の処理を適切に行う必要があります。

ここでは、エラー処理を含む二分探索のサンプルコードを紹介します。

#include <iostream>
#include <vector>
#include <stdexcept>

int binarySearchWithErrorHandling(const std::vector<int>& arr, int target) {
    if (arr.empty()) {
        throw std::invalid_argument("空の配列が渡されました。");
    }

    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid; // 見つかった場合、インデックスを返す
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    throw std::out_of_range("検索対象の値が配列内に存在しません。");
}

int main() {
    try {
        std::vector<int> data = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
        int target = 21;
        int result = binarySearchWithErrorHandling(data, target);
        std::cout << "要素はインデックス " << result << " にあります。\n";
    } catch (const std::exception& e) {
        std::cerr << "エラー: " << e.what() << std::endl;
    }
    return 0;
}

このコードでは、配列が空である場合や検索対象の値が配列内に存在しない場合に、適切な例外を投げてエラーを報告します。

これにより、プログラムの安全性と堅牢性が向上します。

●二分探索の応用例

二分探索は、その基本的な形では非常に強力ですが、さまざまな応用例を通じてその真価を発揮します。

ここでは、ソートされた配列での探索から始まり、より複雑なデータ構造での探索、パフォーマンスの最適化、さらには特定の問題解決に至るまで、いくつかの応用例を紹介します。

○サンプルコード4：ソートされた配列での探索

ソートされた配列での二分探索は最も基本的な応用例の一つです。

下記のサンプルコードでは、ソートされた整数配列内で特定の値を二分探索により探索しています。

#include <iostream>
#include <vector>

int binarySearchInSortedArray(const std::vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    std::vector<int> data = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int target = 14;
    int result = binarySearchInSortedArray(data, target);
    if (result != -1) {
        std::cout << "要素はインデックス " << result << " にあります。\n";
    } else {
        std::cout << "要素は配列内に存在しません。\n";
    }
    return 0;
}

このコードでは、ソートされた配列を対象として、指定された値の位置を効率的に探索しています。

○サンプルコード5：複雑なデータ構造での探索

複雑なデータ構造、例えばオブジェクトの配列やリストでの探索にも二分探索を適用できます。

下記のコードでは、特定の属性を持つオブジェクトの配列を二分探索しています。

#include <iostream>
#include <vector>
#include <algorithm>

class MyObject {
public:
    int key;
    std::string value;

    MyObject(int key, std::string value) : key(key), value(value) {}

    // ソートと比較のための関数
    bool operator < (const MyObject& other) const {
        return key < other.key;
    }
};

int binarySearchInComplexStructure(const std::vector<MyObject>& arr, int targetKey) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid].key == targetKey) {
            return mid;
        } else if (arr[mid].key < targetKey) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    std::vector<MyObject> data = {{1, "A"}, {3, "B"}, {5, "C"}, {7, "D"}, {9, "E"}};
    int targetKey = 5;
    int result = binarySearchInComplexStructure(data, targetKey);
    if (result != -1) {
        std::cout << "キー " << targetKey << " の要素はインデックス " << result << " にあります。\n";
    } else {
        std::cout << "キー " << targetKey << " の要素は配列内に存在しません。\n";
    }
    return 0;
}

この例では、MyObjectクラスのインスタンスがソートされた配列に格納され、特定のキーを持つオブジェクトを効率的に探索しています。

○サンプルコード6：パフォーマンス最適化

二分探索はパフォーマンスの最適化にも役立ちます。

特に、大規模なデータセットや高頻度の検索要求がある場合に、線形探索よりも大幅に効率的です。

下記のサンプルコードでは、大きなデータセットでの二分探索の効率性を表しています。

#include <iostream>
#include <vector>
#include <chrono>

int main() {
    std::vector<int> largeData(1000000);
    // データセットを初期化
    for (int i = 0; i < 1000000; ++i) {
        largeData[i] = i;
    }

    int target = 999999; // 探索対象の値
    auto start = std::chrono::high_resolution_clock::now();
    int result = binarySearchInSortedArray(largeData, target);
    auto end = std::chrono::high_resolution_clock::now();

    std::chrono::duration<double, std::milli> elapsed = end - start;
    std::cout << "検索にかかった時間: " << elapsed.count() << " ミリ秒\n";
    return 0;
}

このコードでは、大きなデータセットにおける二分探索の実行時間を計測し、その効率性を確認しています。

○サンプルコード7：二分探索を使った問題解決

二分探索は、特定の問題を解決するためにも使用できます。

例えば、数値の範囲内で特定の条件を満たす最小または最大の値を見つける場合などです。

下記のサンプルコードでは、このような問題を解決するための二分探索のアプローチを表しています。

#include <iostream>
#include <vector>

bool isConditionMet(int value) {
    // この関数は、特定の条件が満たされるかどうかを判定します。
    // ここでは例として、値が特定の閾値以上であることを条件とします。
    return value >= 500;
}

int findMinimumValueMeetingCondition() {
    int low = 0, high = 1000;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (isConditionMet(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

int main() {
    int result = findMinimumValueMeetingCondition();
    std::cout << "条件を満たす最小の値: " << result << std::endl;
    return 0;
}

このコードでは、特定の条件を満たす最小値を効率的に見つけ出すために二分探索を使用しています。

●二分探索の注意点と対処法

二分探索を使用する際には、いくつかの重要な注意点があります。

これらの注意点を理解し、適切に対処することで、二分探索の効果を最大限に引き出すことができます。

○エッジケースの処理

二分探索では、いくつかのエッジケースが発生する可能性があります。

例えば、空の配列が渡された場合や、検索対象の値が配列の範囲外にある場合などです。

これらのケースを適切に処理することで、プログラムの安定性と信頼性を保つことができます。

ここでは、エッジケースを処理する二分探索のサンプルコードを紹介します。

#include <iostream>
#include <vector>

int binarySearchWithEdgeCases(const std::vector<int>& arr, int target) {
    if (arr.empty()) {
        return -1; // 空の配列が渡された場合
    }

    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // 要素が見つからない場合
}

int main() {
    std::vector<int> data = {1, 3, 5, 7, 9};
    int target = 4;
    int result = binarySearchWithEdgeCases(data, target);
    if (result != -1) {
        std::cout << "要素はインデックス " << result << " にあります。\n";
    } else {
        std::cout << "要素は配列内に存在しません。\n";
    }
    return 0;
}

このコードでは、空の配列や要素が見つからない場合に-1を返すことで、エッジケースを処理しています。

○パフォーマンスとメモリの最適化

二分探索の効率性は非常に高いですが、特に大規模なデータセットを扱う場合には、パフォーマンスとメモリ使用の最適化が重要になります。

例えば、中間値の計算においてオーバーフローを避けるために、midの計算方法を工夫することが挙げられます。

また、不必要なコピーを避けるために、配列の代わりにベクターやイテレータを使用することも有効です。

int binarySearchOptimized(const std::vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // オーバーフローを避ける
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

このように、midの計算式をlow + (high - low) / 2とすることで、大きなインデックス値を扱う際のオーバーフローを防ぐことができます。

また、データのコピーを避けるために、可能な限り参照やイテレータを利用することが推奨されます。

●C++の二分探索のカスタマイズ方法

C++における二分探索は、様々な方法でカスタマイズすることが可能です。

これにより、特定の要件やデータ構造に適した効率的な探索アルゴリズムを構築することができます。

カスタマイズの方法としては、アルゴリズムの挙動を変更することや、異なるデータ型に適応させることなどがあります。

○アルゴリズムのカスタマイズ

二分探索アルゴリズムの挙動をカスタマイズする一つの方法は、比較のロジックを変更することです。

例えば、特定の条件を満たす最初または最後の要素を見つけるために二分探索を利用する場合、比較のロジックを調整することでこれを実現できます。

ここでは、特定の条件を満たす最初の要素を見つけるためのカスタマイズされた二分探索のサンプルコードを紹介します。

#include <iostream>
#include <vector>

int customBinarySearch(const std::vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    int result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= target) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    std::vector<int> data = {1, 2, 2, 3, 3, 3, 4};
    int target = 3;
    int result = customBinarySearch(data, target);
    if (result != -1) {
        std::cout << "条件を満たす最初の要素はインデックス " << result << " にあります。\n";
    } else {
        std::cout << "条件を満たす要素は配列内に存在しません。\n";
    }
    return 0;
}

このコードでは、指定された値以上の最初の要素の位置を探索しています。

○ユーザー定義型での二分探索

C++における二分探索は、ユーザー定義型にも適用することが可能です。

これには、比較関数をカスタマイズすることが含まれます。

ここでは、ユーザー定義型のオブジェクトの配列で二分探索を行うサンプルコードを紹介します。

#include <iostream>
#include <vector>
#include <algorithm>

class MyData {
public:
    int id;
    std::string name;

    MyData(int id, std::string name) : id(id), name(name) {}

    // ソートと比較のための関数
    bool operator < (const MyData& other) const {
        return id < other.id;
    }
};

int binarySearchCustomType(const std::vector<MyData>& arr, int targetId) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid].id == targetId) {
            return mid;
        } else if (arr[mid].id < targetId) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    std::vector<MyData> data = {{1, "Alice"}, {2, "Bob"}, {3, "Charlie"}, {4, "Dave"}};
    int targetId = 2;
    int result = binarySearchCustomType(data, targetId);
    if (result != -1) {
        std::cout << "ID " << targetId << " の要素はインデックス " << result << " にあります。\n";
    } else {
        std::cout << "ID " << targetId << " の要素は配列内に存在しません。\n";
    }
    return 0;
}

このコードでは、ユーザー定義型のオブジェクトの配列を対象に二分探索を行い、指定されたIDを持つオブジェクトの位置を探索しています。

このように、比較ロジックをカスタマイズすることで、様々なデータ型に二分探索を適用することが可能です。

まとめ

この記事では、C++における二分探索の基本から応用、注意点、そしてカスタマイズ方法までを詳細に解説しました。

基本的な実装から、エッジケースの処理、さらにはユーザー定義型やアルゴリズムのカスタマイズに至るまで、実用的なサンプルコードを用いて理解を深めることができます。

これにより、C++での二分探索を効果的に利用し、様々な問題を解決する力を身につけることが可能です。

プログラマーとしてのスキルを高めるために、是非ともこの強力なツールを活用してください。