37. Linear Search

선형 탐색(Linear Search)은 주어진 데이터에서 원하는 데이터를 찾는 가장 기본적인 방법으로, 순차 탐색(Sequential Search)이라고도 한다. 주어진 데이터가 정렬되어 있지 않는 경우에도 사용할 수 있지만 모든 데이터를 다 확인할 수도 있기 때문에 시간복잡도가 $O(n)$으로 다른 빠른 탐색에 비해 상대적으로 느리다는 단점이 존재한다.

 

다음은 $n$개의 원소로 이루어진 배열 $a$에서 $k$라는 값을 찾는 코드의 일부이다. 인덱스는 $1$-based이다.

int pos = 0;
for(int i = 1; i <= n; i++)
{
    if(a[i] == k)pos = i;
}

pos는 position을 의미하며 인덱스를 저장하는 식별자로 많이 사용된다.

위의 코드는 매우 간단하며 다양하게 응용할 수 있다. 주어진 데이터의 최대값, 최소값을 찾거나 중복된 원소가 포함된 데이터에서 원하는 데이터의 위치를 모두 찾는 등, 반복문 내부의 조건문을 변형하여 다양한 작업을 할 수 있다. 하지만 탐색 자체를 많이 실행해야 할 경우 선형 탐색은 효율성이 너무 떨어질 수 있다. 이때 데이터가 정렬되어 있는 등 특수한 경우에 해당한다면 다음에 나올 더 빠른 정렬을 이용할 수 있다.