C++で特定の配列内の要素を線形に検索する再帰プログラム

任意の順序で整数を含む整数配列Arr[]が与えられます。目標は、配列の再帰検索を使用して、配列に存在する入力整数値を見つけることです。

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

例

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

出力 −インデックス5で26が見つかりました

説明 −

Elements in the array start from index 0 to index=array length -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 is present at index 5.

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

出力 −66は存在しません

説明 −

Elements in the array start from index 0 to index=array length -1.
First index=0 last index=6 : 11 != 66, 78 != 66 → 0+1 , 6-1
First index=1 last index=5 : 66 != 26, 66 != 26 → 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 != 26, 50 != 26 → 3+1 , 3-1
First index=3 last index=2 3>2 end
66 not found.

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、アレイを両端から直線的にトラバースします。入力値を両端の要素と比較します。見つかった場合は、インデックスを返します。それ以外の場合は、最初のインデックス=前の最初のインデックス+1と最後のインデックス=前の最後のインデックス-1の次の要素を再帰的にチェックします。最初のインデックス>最後のインデックスの場合、要素が見つかりません。

• 整数要素を持つ入力配列Ar[]を取ります。

• 検索する要素をvalとして取得します。

• 関数searchRec（int arr []、int start、int end、int num）は、配列、最初と最後のインデックス、および検索される値numを受け取り、見つかった場合はインデックスを返します。

• 変数の結果を-99とします。

• arr [start] ==numの場合、結果をstartとして設定します

• arr [end] ==numの場合、結果をendとして設定します

• if（start> end）then set result=-1。アレイ全体をトラバースしたとき

• 結果の値が-99以外の場合は、結果を返します。それ以外の場合は、searchRec（arr、start + 1、end -1、num）を使用して再帰的に検索します

• メインチェックの内部で戻り値を確認し、それに応じて結果を出力します

例

#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