순차 검색

컴퓨터 과학에서 선형 검색(linear search) 또는 순차 검색(sequential search)은 리스트 내에서 요소를 찾는 방법이다. 일치하는 항목을 찾거나 전체 리스트를 검색할 때까지 리스트의 각 요소를 순차적으로 확인한다.

선형 검색은 선형 시간에 실행되며 최악의 경우 최대 번의 비교를 수행한다. 여기서 은 리스트의 길이이다. 각 요소가 동등하게 검색될 가능성이 있다면, 선형 검색은 평균적으로 번의 비교를 수행하지만, 각 요소에 대한 검색 확률이 다르면 평균 사례에 영향을 미칠 수 있다. 이진 검색 알고리즘 및 해시 테이블과 같은 다른 검색 알고리즘 및 체계는 짧은 리스트를 제외하고는 훨씬 빠른 검색을 허용하기 때문에 선형 검색은 드물게 실용적이다.

알고리즘
선형 검색은 대상 값과 일치하는 요소를 찾을 때까지 리스트의 각 요소를 순차적으로 확인한다. 만약 알고리즘이 리스트의 끝에 도달하면 검색은 실패로 종료된다.

기본 알고리즘
값 또는 레코드 를 가진 개의 요소로 이루어진 리스트 와 대상 값 가 주어졌을 때, 다음 서브루틴은 선형 검색을 사용하여 에서 대상 의 인덱스를 찾는다.

 를 0으로 설정한다.
 만약 이면, 검색은 성공적으로 종료되고 를 반환한다.
 를 1 증가시킨다.
 만약 이면, 2단계로 이동한다. 그렇지 않으면 검색은 실패로 종료된다.

센티넬 사용
위의 기본 알고리즘은 각 반복마다 두 번의 비교를 수행한다. 하나는 가 T와 같은지 확인하는 것이고, 다른 하나는 가 여전히 유효한 리스트 인덱스를 가리키는지 확인하는 것이다. 리스트에 대상과 같은 추가 레코드  (즉, 센티넬 값)를 추가함으로써, 검색이 끝날 때까지 두 번째 비교를 제거하여 알고리즘을 더 빠르게 만들 수 있다. 대상이 리스트에 포함되어 있지 않으면 검색은 센티넬에 도달할 것이다.

 를 0으로 설정한다.
 만약 이면, 4단계로 이동한다.
 를 1 증가시키고 2단계로 이동한다.
 만약 이면, 검색은 성공적으로 종료되고 를 반환한다. 그렇지 않으면 검색은 실패로 종료된다.

정렬된 테이블에서
리스트가 와 같이 정렬되어 있다면, 가 대상보다 커지면 검색을 종료하여 대상의 부재를 더 빨리 확립할 수 있다. 이 변형은 대상보다 큰 센티넬을 필요로 한다.

 를 0으로 설정한다.
 만약 이면, 4단계로 이동한다.
 를 1 증가시키고 2단계로 이동한다.
 만약 이면, 검색은 성공적으로 종료되고 를 반환한다. 그렇지 않으면 검색은 실패로 종료된다.

분석
n개의 항목이 있는 리스트의 경우, 최상의 경우는 찾는 값이 리스트의 첫 번째 요소와 같을 때이며, 이 경우 단 하나의 비교만 필요하다. 최악의 경우는 찾는 값이 리스트에 없거나 (또는 리스트의 끝에 한 번만 나타나는 경우)이며, 이 경우 n번의 비교가 필요하다.

찾는 값이 리스트에 k번 나타나고, 리스트의 모든 순서가 동일하게 가능성이 있다면, 예상 비교 횟수는 다음과 같다.

예를 들어, 찾는 값이 리스트에 한 번 나타나고, 리스트의 모든 순서가 동일하게 가능성이 있다면, 예상 비교 횟수는 이다. 그러나 한 번 나타난다는 것을 알고 있다면, 최대 n − 1번의 비교가 필요하며, 예상 비교 횟수는 다음과 같다.

(예를 들어, n = 2일 경우 이는 1이며, 단일 if-then-else 구조에 해당한다.)

어떤 경우든, 점근적으로 선형 검색의 최악의 경우 비용과 예상 비용은 모두 O(n)이다.

균일하지 않은 확률
선형 검색의 성능은 원하는 값이 리스트의 끝보다 시작 부분에 있을 가능성이 더 높을 때 향상된다. 따라서 일부 값이 다른 값보다 검색될 가능성이 훨씬 높다면, 이들을 리스트의 시작 부분에 배치하는 것이 바람직하다.

특히, 리스트 항목이 확률 감소 순서로 배열되고 이 확률이 기하 분포를 따를 때, 선형 검색의 비용은 O(1)에 불과하다.  

일반적으로, 항목이 확률 감소 순서로 배열되어 있고 i번째 요소에 대한 검색 확률이 일 때, 단일 검색의 예상 비용은 이다. 확률을 미리 알 수 없거나 확률에 따라 리스트를 정렬할 시간이 없다는 자연스러운 가정 하에, 자체 조정 데이터 구조 방식을 사용하여 검색에서 요청될 때 요소를 리스트의 맨 앞으로 이동시킬 수 있다.
이러한 자체 조정에 대한 두 가지 자연스러운 휴리스틱은 이동 전면(Move to Front, MF)과 전치(Transpose, T)이며, 요청된 요소는 그 선행 요소와 자리를 바꾼다. 독립적인 접근의 큰 시퀀스에서 접근의 예상 비용은 리스트의 모든 초기 순서에 대해 평균을 내면 를 만족하는 것으로 알려져 있다.
분할 상환 비용 측면에서, 최악의 연산 시퀀스에 대해 평균을 내면(확률에 대한 가정을 만족하는 시퀀스 중에서), 가 되는 반면, 는 만큼 나쁠 수 있다. 

응용
선형 검색은 일반적으로 구현이 매우 간단하며, 리스트에 요소가 몇 개 없거나 정렬되지 않은 리스트에서 단일 검색을 수행할 때 실용적이다.

같은 리스트에서 많은 값을 검색해야 할 때, 더 빠른 방법을 사용하기 위해 리스트를 전처리하는 것이 종종 이득이 된다. 예를 들어, 리스트를 정렬하고 이진 검색을 사용하거나, 효율적인 검색 자료 구조를 만들 수 있다. 리스트의 내용이 자주 변경되는 경우, 반복적인 재정렬은 그만한 가치가 없을 수도 있다.

결과적으로, 이론적으로 다른 검색 알고리즘이 선형 검색보다 빠를 수 있지만(예를 들어 이진 검색), 실제로는 중간 크기의 배열(100개 항목 이하)에서도 다른 것을 사용하는 것이 비실용적일 수 있다. 더 큰 배열에서는 데이터 정렬과 같은 초기 준비 시간이 많은 선형 검색과 비슷하기 때문에 데이터가 충분히 클 경우에만 다른, 더 빠른 검색 방법을 사용하는 것이 합리적이다.

 소스 코드 
 파이썬 
def sequentialSearch(array, value):
	for i in range(len(array)):
		if array[i] == value:
			return i
	return False

 C언어 
int sequentialSearch(int array[], int n, int m, int value) { // Starts from n to m
    int i;
    for (i = n; i <= m; i++)
        if (array[i] == value)
            return i;
    return -1;
}

 같이 보기 
 삼진 검색
 해시 테이블
 선형 탐색 문제

 각주 
인용

저서


분류:검색 알고리즘