임의의 순서로 정수를 포함하는 정수 배열 Arr[]이 제공됩니다. 목표는 배열에 대한 재귀 검색을 사용하여 배열에 있는 입력 정수 val을 찾는 것입니다.
입력 배열 Arr[]에 val이 없으면 -1을 반환합니다. Arr[]에 있는 경우 val의 인덱스를 인쇄합니다.
예시
입력 -Arr[] ={11,43,24,50,93,26,78} val=26
출력 − 26은 인덱스 5에서 찾음
설명 -
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인 다음 요소를 재귀적으로 확인합니다. 첫 번째 index>마지막 indexthen 요소가 없는 경우
-
정수 요소가 있는 입력 배열 Ar[]을 가져옵니다.
-
검색할 요소를 val로 가져옵니다.
-
searchRec(int arr[], int start,int end, int num) 함수는 배열, 검색할 첫 번째 및 마지막 인덱스 및 값 num을 취하여 찾은 경우 인덱스를 반환합니다.
-
변수 결과를 -99로 취하십시오.
-
arr[start] ==num이면 결과를 시작으로 설정
-
arr[end] ==num이면 결과를 끝으로 설정
-
if (start> end) 결과=-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