動的配列を使った C++ の二分探索

はじめに

二分探索は、ソート済み配列内の要素のインデックス位置を見つける探索方法です。C++ では、2 つのアプローチ（反復的および再帰的）を使って二分探索を行うことができます。この実験では、動的配列を使って二分探索操作を行います。

新しい C++ ファイルを作成する

まず、~/project ディレクトリに main.cpp という名前の新しい C++ ファイルを作成します。

touch ~/project/main.cpp

ヘッダーファイルをインクルードする

次に、必要なヘッダーファイル iostream、algorithm、および vector をインクルードします。

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

using namespace std;

動的配列を作成して要素で埋める

vector クラスを使って整数の動的配列を作成し、ソート済みの整数で埋めます。

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

二分探索関数を実装する

次に、反復的なアプローチを使ってソート済み配列内の要素のインデックス位置を検索する二分探索関数を実装します。

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

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

二分探索関数を呼び出して結果を出力する

最後に、探索対象の要素を使って二分探索関数を呼び出し、結果をコンソールに出力します。

int target = 7;
int result = binarySearch(arr, target);

if (result == -1) {
    cout << "Element not found!" << endl;
} else {
    cout << "Element found at index " << result << endl;
}

プログラムをコンパイルして実行する

次のコマンドを実行することで、端末でプログラムをコンパイルして実行します。

g++ main.cpp -o main &&./main

最終コード

ここにmain.cppファイルの完全なコードを示します。

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

using namespace std;

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

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

    if (result == -1) {
        cout << "Element not found!" << endl;
    } else {
        cout << "Element found at index " << result << endl;
    }

    return 0;
}

まとめ

この実験では、C++ で動的配列を使って二分探索を行う方法を学びました。反復的なアプローチを使い、ソート済み配列内の要素のインデックス位置を検索する二分探索関数を実装しました。また、C++ のvectorクラスを使って動的配列を作成する方法も学びました。

動的配列を使った CPP の二分探索