선형 검색(Linear Search)으로 배열의 최솟값을 찾는 C++ 프로그램

이 글에서는 선형 검색(Linear Search) 방식을 활용해 배열에서 최소 요소를 찾는 C++ 프로그램을 소개합니다. 선형 검색은 배열의 첫 번째 요소부터 마지막 요소까지 순서대로 하나씩 비교해가는 가장 기본적인 탐색 기법으로, 이 프로그램의 시간 복잡도는 O(n)입니다.

알고리즘

선형 검색으로 배열의 최솟값을 찾는 절차는 다음과 같습니다.

Begin
   배열에 데이터 요소를 저장한다.
   인덱스 '0'에 있는 값을 minimum 변수에 대입한다.
   minimum 값을 배열의 나머지 요소들과 순서대로 비교한다.
   특정 인덱스의 값이 현재 minimum보다 작으면 그 값으로 교체한다.
   모든 요소를 확인한 뒤 최종 minimum 값을 출력한다.
End

예제 코드

아래 코드는 크기가 10인 배열을 선언한 뒤, 반복문을 통해 각 요소를 출력하면서 동시에 최솟값을 갱신하는 방식으로 동작합니다.

#include<iostream>
using namespace std;
int main() {
   int n, i, minimum, a[10] = {1, 6, 7, 10, 12, 14, 12, 16, 20, 26};
   char ch;
   minimum = a[0];
   cout<<"\nThe data element of array:";
   for(i = 0; i < 10; i++) {
      cout<<" "<<a[i];
      if(minimum > a[i])
         minimum= a[i];
   }
   cout<<"\n\nMinimum of the data elements of array using linear search is: "<<minimum;
   return 0;
}

코드 동작 원리

먼저 배열의 첫 번째 요소 a[0] 값을 minimum 변수에 저장하여 초기 후보로 설정합니다. 이후 for 반복문이 배열을 처음부터 끝까지 순회하면서, 현재 minimum보다 더 작은 값을 발견할 때마다 해당 값으로 minimum을 갱신합니다. 반복문이 종료되면 minimum에는 배열 전체에서 가장 작은 값이 남아 있게 됩니다.

이처럼 최댓값·최솟값을 찾는 문제는 배열을 한 번만 순회하면 해결할 수 있으므로, 데이터 개수가 n일 때 시간 복잡도는 O(n)이 되며 추가적인 메모리 사용 없이 제자리(in-place)에서 처리할 수 있다는 장점이 있습니다.

실행 결과

The data element of array: 1 6 7 10 12 14 12 16 20 26
Minimum of the data elements of array using linear search is: 1

실행 결과를 보면 배열의 모든 요소가 먼저 출력되고, 그다음 줄에 선형 검색을 통해 찾아낸 최솟값 1이 정상적으로 표시되는 것을 확인할 수 있습니다.