개요
정수들이 임의의 순서로 저장된 정수 배열 Arr[]이 주어졌을 때, 배열에 대한 재귀(recursion) 탐색을 이용해 입력 정수 val이 배열 안에 존재하는지 찾는 것이 목표입니다.
만약 val이 배열 Arr[]에서 발견되지 않으면 -1을 반환하고, 발견된 경우에는 해당 값의 인덱스(index)를 출력합니다.
예제
입력 − Arr[] = {11, 43, 24, 50, 93, 26, 78}, val = 26
출력 − 26 found at index 5
설명 −
배열의 요소는 인덱스 0부터 인덱스 (배열 길이 - 1)까지 존재합니다. 첫 번째 인덱스=0, 마지막 인덱스=6 : 11 != 26, 78 != 26 → 0+1, 6-1 첫 번째 인덱스=1, 마지막 인덱스=5 : 43 != 26, 26 == 26 → 5 반환 26은 인덱스 5에 존재합니다.
입력 − Arr[] = {11, 43, 24, 50, 93, 26, 78}, val = 66
출력 − 66 is not present
설명 −
배열의 요소는 인덱스 0부터 인덱스 (배열 길이 - 1)까지 존재합니다. 첫 번째 인덱스=0, 마지막 인덱스=6 : 11 != 66, 78 != 66 → 0+1, 6-1 첫 번째 인덱스=1, 마지막 인덱스=5 : 43 != 66, 78 != 66 → 1+1, 5-1 첫 번째 인덱스=2, 마지막 인덱스=4 : 24 != 66, 93 != 66 → 2+1, 4-1 첫 번째 인덱스=3, 마지막 인덱스=3 : 50 != 66 → 3+1, 3-1 첫 번째 인덱스=4 > 마지막 인덱스=3 → 탐색 종료 66은 배열에서 발견되지 않았습니다.
프로그램에서 사용하는 접근 방식
이 방식에서는 배열을 양쪽 끝에서 동시에 선형적으로 순회(traverse)합니다. 입력값과 양 끝 위치의 요소를 비교하고, 일치하는 값을 찾으면 그 인덱스를 반환합니다. 찾지 못했다면 시작 인덱스는 이전 시작 인덱스 + 1로, 마지막 인덱스는 이전 마지막 인덱스 - 1로 갱신한 뒤 재귀적으로 다시 탐색을 진행합니다. 만약 시작 인덱스가 마지막 인덱스보다 커지면(start > end) 배열 전체를 탐색한 것이므로 해당 요소는 배열에 존재하지 않습니다.
정수 요소들을 가진 입력 배열 Ar[]을 준비합니다.
검색할 대상 값을 val로 받습니다.
함수 searchRec(int arr[], int start, int end, int num)는 배열, 첫 번째/마지막 인덱스, 그리고 검색할 값 num을 매개변수로 받아, 값을 찾으면 해당 인덱스를 반환합니다.
결과를 저장할 변수 result를 -99로 초기화합니다(아직 찾지 못했음을 의미).
만약 arr[start] == num이라면 result를 start로 설정합니다.
만약 arr[end] == num이라면 result를 end로 설정합니다.
start > end라면 result를 -1로 설정합니다. 배열 전체를 탐색했다는 의미입니다.
result가 -99 이외의 값을 가지면 result를 반환하고, 그렇지 않으면 searchRec(arr, start + 1, end - 1, num)으로 재귀 호출하여 탐색을 계속합니다.
main 함수 내부에서 반환값을 확인하고 결과에 맞게 출력합니다.
구현 예제 코드
#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