C++で配列内の要素を両端から再帰的に線形検索するプログラム

整数型配列 Arr[] には、任意の順序で整数が格納されています。この記事の目標は、配列に対して再帰的な探索を行い、指定された整数 val が配列内に存在するかどうかを見つけることです。

もし val が配列 Arr[] 内に見つからない場合は -1 を返します。見つかった場合は、そのインデックス（添字）を出力します。

実行例

例1：値が見つかる場合

入力： Arr[] = {11,43,24,50,93,26,78}, val = 26

出力： 26 found at index 5

解説：

配列の要素はインデックス 0 から「配列長 - 1」まで走査される。
First index=0, Last index=6 : 11 != 26, 78 != 26 → 0+1, 6-1
First index=1, Last index=5 : 43 != 26, 26 == 26 → return 5

26 はインデックス 5 に存在する。

例2：値が見つからない場合

入力： Arr[] = {11,43,24,50,93,26,78}, val = 66

出力： 66 is not present

解説：

配列の要素はインデックス 0 から「配列長 - 1」まで走査される。
First index=0, Last index=6 : 11 != 66, 78 != 66 → 0+1, 6-1
First index=1, Last index=5 : 43 != 66, 26 != 66 → 1+1, 5-1
First index=2, Last index=4 : 24 != 66, 93 != 66 → 2+1, 4-1
First index=3, Last index=3 : 50 != 66, 50 != 66 → 3+1, 3-1
First index=4, Last index=2 : start > end となり探索終了

66 は配列内に存在しない。

アルゴリズムの考え方

この手法では、配列を両端から同時に線形に走査していきます。具体的には以下の手順です。

• 入力値と、配列の先頭・末尾の要素をそれぞれ比較します。
• 一致する要素が見つかれば、そのインデックスを返します。
• 見つからなければ、先頭インデックスを +1、末尾インデックスを -1 して、再帰的に次の要素を確認します。
• 先頭インデックスが末尾インデックスを超えた場合（start > end）、配列全体を走査し終えたことになるため、要素は存在しないと判断します。

処理手順

1. 整数要素を含む配列 Arr[] を用意します。
2. 探索対象の値 val を設定します。
3. 関数 searchRec(int arr[], int start, int end, int num) は、配列・先頭インデックス・末尾インデックス・探索値を受け取り、見つかればそのインデックスを返します。
4. 変数 result を -99 で初期化します（未検出を表すフラグ値）。
5. arr[start] == num なら、result に start を代入します。
6. arr[end] == num なら、result に end を代入します。
7. start > end の場合は、配列全体を走査済みなので result = -1 とします。
8. result が -99 以外の値を持っていればそれを返し、そうでなければ searchRec(arr, start + 1, end - 1, num) で再帰的に探索を続けます。
9. main 関数内で戻り値を判定し、結果に応じてメッセージを出力します。

C++ 実装コード

#include<bits/stdc++.h>
using namespace std;
int searchRec(int arr[], int start,int end, int num){
    int result=-99;
    if (start > end){
        result= -1;
    }
    if (arr[start] == num){
        result=start;
    }
    if (arr[end] == num){
        result=end;
    }
    if( result!=-99){
        return result;
    }
    return searchRec(arr, start + 1, end - 1, num);
}
int main(){
    int Arr[] = {11,43,22,56,33,26,78};
    int i;
    int len = sizeof(Arr) / sizeof(Arr[0]);
    int val = 56;
    int pos = searchRec(Arr, 0, len - 1, val);
    if (pos == -1){
        cout<<val<<" is not present" ;
    }
    else{
        cout<<val<<" found at index "<<pos;
    }
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

56 found at index 3

まとめ

このプログラムでは、再帰呼び出しを使って配列を両端から中央に向かって走査することで、線形検索を実現しています。計算量は O(n) であり、配列がソートされていない場合でも適用できるシンプルな探索手法です。なお、再帰の深さが配列サイズに依存するため、非常に大きな配列を扱う場合はスタックオーバーフローに注意が必要です。