이 글에서는 배열 안에서 특정 요소를 재귀(Recursion) 방식으로 선형 검색하는 방법을 자세히 살펴보겠습니다. 선형 검색(Linear Search)은 모든 항목을 처음부터 끝까지 하나씩 순차적으로 확인하는 가장 기본적인 검색 알고리즘입니다.
선형 검색이란?
선형 검색은 배열의 첫 번째 요소부터 마지막 요소까지 차례대로 목표 값과 비교하다가, 일치하는 값을 찾으면 그 위치(인덱스)를 반환하는 방식입니다. 이번 예제에서는 양쪽 끝(l, r)에서 동시에 탐색 범위를 좁혀 오는 재귀 호출 구조를 사용합니다.
입력 및 출력 예시
입력값이 다음과 같다고 가정해 보겠습니다.
입력 배열: 14 20 35 47 50 65 72 81 90 99 검색할 키 요소: 72
원하는 출력 결과는 다음과 같습니다.
요소 72는 위치(인덱스): 6 에 존재합니다.
알고리즘
1단계 - 시작(START) 2단계 - 배열 input_array와 정수 변수 key_element, index를 선언한다. 3단계 - 배열의 값을 정의한다. 4단계 - 배열을 순회하며 탐색을 진행한다. 5단계 - 검색할 요소(key)를 정의하고, 필요한 매개변수를 전달하여 재귀 메서드를 호출한다. 6단계 - 조건문(if)을 정의한다. 검색에 실패하면 -1을, 성공하면 해당 요소의 인덱스를 반환한다. 7단계 - 결과를 콘솔에 출력한다. 8단계 - 종료(STOP)
예제 1: 정수 배열 선형 검색
다음 예제는 정수 배열에서 재귀적 선형 검색을 수행하는 코드입니다.
public class LinearSearch {
static int recSearch(int input_array[], int l, int r, int key_element) {
if (r < l)
return -1;
if (input_array[l] == key_element)
return l;
if (input_array[r] == key_element)
return r;
return recSearch(input_array, l+1, r-1, key_element);
}
public static void main(String[] args) {
int input_array[] = {14, 20, 35, 47, 50, 65, 72, 81, 90, 99};
System.out.println("배열의 요소는 아래와 같습니다.");
for (int i : input_array) {
System.out.print(i +" ");
}
int key_element = 72;
System.out.println("\n\n배열에서 검색할 요소: " + key_element);
int index = recSearch(input_array, 0, input_array.length-1, key_element);
if (index != -1)
System.out.println("\n요소 " + key_element + "는 위치 " + index + "에 존재합니다.");
else
System.out.println("요소 " + key_element + "는 배열에 존재하지 않습니다.");
}
}
실행 결과
배열의 요소는 아래와 같습니다. 14 20 35 47 50 65 72 81 90 99 배열에서 검색할 요소: 72 요소 72는 위치 6에 존재합니다.
코드 동작 원리
recSearch 메서드는 탐색 범위의 양쪽 경계를 나타내는 두 매개변수 l(왼쪽 끝)과 r(오른쪽 끝)를 사용합니다.
r < l이면 더 이상 탐색할 범위가 없으므로-1을 반환하여 검색 실패를 나타냅니다.input_array[l]또는input_array[r]이 키 값과 일치하면 해당 인덱스를 즉시 반환합니다.- 일치하지 않으면
l+1,r-1로 탐색 범위를 좁혀가며 자기 자신을 다시 호출(재귀)합니다.
반환되는 값은 0부터 시작하는 배열 인덱스입니다. 따라서 위 실행 결과의 "위치 6"은 일곱 번째 요소(72)를 의미합니다.
예제 2: 문자열 배열 선형 검색
다음 예제는 동일한 로직을 문자열(String) 배열에 적용한 코드입니다. 자바에서 문자열 내용을 비교할 때는 참조를 비교하는 == 연산자 대신 equals() 메서드를 사용해야 한다는 점에 유의하세요.
public class Demo {
static int recSearch(String input_array[], int l, int r, String key_element) {
if (r < l)
return -1;
if (input_array[l].equals(key_element))
return l;
if (input_array[r].equals(key_element))
return r;
return recSearch(input_array, l+1, r-1, key_element);
}
public static void main(String[] args) {
String input_array[] = { "Scala", "Java", "Python", "Mysql"};
System.out.println("배열의 요소는 아래와 같습니다.");
for (String i : input_array) {
System.out.print(i +" ");
}
String key_element = "Java";
System.out.println("\n\n배열에서 검색할 요소: " + key_element);
int index = recSearch(input_array, 0, input_array.length-1, key_element);
if (index != -1)
System.out.println("\n요소 " + key_element + "는 위치 " + index + "에 존재합니다.");
else
System.out.println("요소 " + key_element + "는 배열에 존재하지 않습니다.");
}
}
실행 결과
배열의 요소는 아래와 같습니다. Scala Java Python Mysql 배열에서 검색할 요소: Java 요소 Java는 위치 1에 존재합니다.
마무리
지금까지 재귀 호출을 활용해 배열에서 요소를 선형 검색하는 방법을 정수 배열과 문자열 배열 두 가지 예제로 살펴보았습니다. 선형 검색의 시간 복잡도는 O(n)으로, 데이터 양이 많아질수록 이진 검색(O(log n))과 같은 알고리즘이 더 유리할 수 있습니다. 다만 정렬되지 않은 배열이나 소량의 데이터를 다룰 때는 선형 검색이 여전히 간단하고 실용적인 선택이 됩니다.