C++ 二分探索 | プログラミングチュートリアル

はじめに

この実験では、C++ を使って修正済みの二分探索を用いて、ソート済み配列内の特定の数値の最初の出現位置を見つける方法を学びます。

C++ コードファイル

まずは、touch テキストエディタを使って ~/project ディレクトリに main.cpp という名前の C++ コードファイルを作成しましょう。

touch ~/project/main.cpp

コードに必要なヘッダーを含める

プログラムに必要な C++ ヘッダーファイルを含める必要があります。以下のコードをコピーして main.cpp ファイルに貼り付けます。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

要素の最初の出現位置を見つける関数を作成する

要素の最初の出現位置を見つけるための関数 first() を作成します。この関数は、配列、その下限インデックス、上限インデックス、および検索対象の要素を入力として受け取ります。この関数は、要素の最初の出現位置のインデックスを返します。main.cpp ファイルに以下のコードを追加します。

int first(int a[], int l, int h, int b)
{
    int res = -1;
    while (l <= h)
    {
        int m = (l + h) / 2;
        if (a[m] == b)
        {
            res = m;
            h = m - 1;
        }
        else if (a[m] > b)
        {
            h = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    return res;
}

ここでは、二分探索を使って要素の最初の出現位置を見つけています。要素が配列に存在しない場合を処理するために、res 変数を -1 で初期化しています。中央の要素が検索対象の要素と等しい場合、中央の要素のインデックスを res に格納し、要素の最初の出現位置を探しているため、上限インデックスを m-1 に更新します。中央の要素が検索対象の要素より大きい場合、上限インデックスを m-1 に更新し、中央の要素が検索対象の要素より小さい場合、下限インデックスを m+1 に更新します。

メイン関数を実装する

メイン関数では、配列を作成し、手順 3 で作成した first 関数に適切な引数を渡して呼び出し、結果をコンソールに出力します。以下のコードを main 関数にコピーして貼り付けます。

int main()
{
    int a[] = {2, 3, 3, 4, 4, 4, 4, 4, 5};

    int n = sizeof(a) / sizeof(a[0]);

    int k = 4; //最初の出現インデックスを見つける要素

    int f = first(a, 0, n - 1, k);

    if(f==-1)
    {
        cout << "要素が見つかりません\n";
    }
    else
    {
        cout << k << " の最初の出現インデックスは：" << f << endl;
    }

    return 0;
}

ここでは、整数型の配列 a を宣言し、ソート済みの整数値で初期化しています。また、sizeof 演算子を使って配列内の要素数を計算しています。その後、適切な引数を使って first() 関数を呼び出し、結果を出力しています。

C++ コードをコンパイルして実行する

これで、以下のコマンドを使って C++ コードをコンパイルして実行できます。

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

すべてがうまくいけば、出力は 4 の最初の出現インデックスは: 3 になります。

まとめ

この実験では、C++ で修正済みの二分探索を使ってソート済み配列内の特定の数の最初の出現位置を見つける方法を学びました。アルゴリズムを実装するために first() 関数を作成しました。

ソート済み配列における最初の出現位置の特定