순차 검색

data= 컴퓨터 과학에서 **선형 검색**(linear search) 또는 **순차 검색**(sequential search)은 리스트 내에서 요소를 찾는 방법이다. 일치하는 항목을 찾거나 전체 리스트를 검색할 때까지 리스트의 각 요소를 순차적으로 확인한다.loc=§6.1 ("Sequential search") 선형 검색은 선형 시간에 실행되며 최악의 경우 최대 n번의 비교를 수행한다. 여기서 n은 리스트의 길이이다. 각 요소가 동등하게 검색될 가능성이 있다면, 선형 검색은 평균적으로 2번의 비교를 수행하지만, 각 요소에 대한 검색 확률이 다르면 평균 사례에 영향을 미칠 수 있다. 이진 검색 알고리즘 및 해시 테이블과 같은 다른 검색 알고리즘 및 체계는 짧은 리스트를 제외하고는 훨씬 빠른 검색을 허용하기 때문에 선형 검색은 드물게 실용적이다.loc=§6.2 ("Searching by Comparison Of Keys")
# 알고리즘
선형 검색은 대상 값과 일치하는 요소를 찾을 때까지 리스트의 각 요소를 순차적으로 확인한다. 만약 알고리즘이 리스트의 끝에 도달하면 검색은 실패로 종료된다.loc=§6.1 ("Sequential search")
## 기본 알고리즘
값 또는 레코드 L0 .... Ln−1를 가진 n개의 요소로 이루어진 리스트 L와 대상 값 T가 주어졌을 때, 다음 서브루틴은 선형 검색을 사용하여 L에서 대상 T의 인덱스를 찾는다.loc=§6.1 ("Sequential search"), subsection "Algorithm B" # i를 0으로 설정한다. # 만약 Li = T이면, 검색은 성공적으로 종료되고 i를 반환한다. # i를 1 증가시킨다. # 만약 i < n이면, 2단계로 이동한다. 그렇지 않으면 검색은 실패로 종료된다.
## 센티넬 사용
위의 기본 알고리즘은 각 반복마다 두 번의 비교를 수행한다. 하나는 Li가 T와 같은지 확인하는 것이고, 다른 하나는 i가 여전히 유효한 리스트 인덱스를 가리키는지 확인하는 것이다. 리스트에 대상과 같은 추가 레코드 Ln (즉, 센티넬 값)를 추가함으로써, 검색이 끝날 때까지 두 번째 비교를 제거하여 알고리즘을 더 빠르게 만들 수 있다. 대상이 리스트에 포함되어 있지 않으면 검색은 센티넬에 도달할 것이다.loc=§6.1 ("Sequential search"), subsection "Algorithm Q" # i를 0으로 설정한다. # 만약 Li = T이면, 4단계로 이동한다. # i를 1 증가시키고 2단계로 이동한다. # 만약 i < n이면, 검색은 성공적으로 종료되고 i를 반환한다. 그렇지 않으면 검색은 실패로 종료된다.
## 정렬된 테이블에서
리스트가 L0 ≤ L1 ... ≤ Ln−1와 같이 정렬되어 있다면, Li가 대상보다 커지면 검색을 종료하여 대상의 부재를 더 빨리 확립할 수 있다. 이 변형은 대상보다 큰 센티넬을 필요로 한다.loc=§6.1 ("Sequential search"), subsection "Algorithm T" # i를 0으로 설정한다. # 만약 Li ≥ T이면, 4단계로 이동한다. # i를 1 증가시키고 2단계로 이동한다. # 만약 Li = T이면, 검색은 성공적으로 종료되고 i를 반환한다. 그렇지 않으면 검색은 실패로 종료된다.
# 분석
n개의 항목이 있는 리스트의 경우, 최상의 경우는 찾는 값이 리스트의 첫 번째 요소와 같을 때이며, 이 경우 단 하나의 비교만 필요하다. 최악의 경우는 찾는 값이 리스트에 없거나 (또는 리스트의 끝에 한 번만 나타나는 경우)이며, 이 경우 n번의 비교가 필요하다. 찾는 값이 리스트에 k번 나타나고, 리스트의 모든 순서가 동일하게 가능성이 있다면, 예상 비교 횟수는 다음과 같다. : \begin{cases} n & \mbox{if } k = 0 \\\\[5pt] \displaystyle\frac{n + 1}{k + 1} & \mbox{if } 1 \le k \le n. \end{cases} 예를 들어, 찾는 값이 리스트에 한 번 나타나고, 리스트의 모든 순서가 동일하게 가능성이 있다면, 예상 비교 횟수는 \frac{n + 1}2이다. 그러나 한 번 나타난다는 것을 알고 있다면, 최대 n − 1번의 비교가 필요하며, 예상 비교 횟수는 다음과 같다. :\displaystyle\frac{(n + 2)(n-1)}{2n} (예를 들어, n = 2일 경우 이는 1이며, 단일 if-then-else 구조에 해당한다.) 어떤 경우든, 점근적으로 선형 검색의 최악의 경우 비용과 예상 비용은 모두 O(n)이다.
## 균일하지 않은 확률
선형 검색의 성능은 원하는 값이 리스트의 끝보다 시작 부분에 있을 가능성이 더 높을 때 향상된다. 따라서 일부 값이 다른 값보다 검색될 가능성이 훨씬 높다면, 이들을 리스트의 시작 부분에 배치하는 것이 바람직하다. 특히, 리스트 항목이 확률 감소 순서로 배열되고 이 확률이 기하 분포를 따를 때, 선형 검색의 비용은 O(1)에 불과하다. pages = 396–408 일반적으로, 항목이 확률 감소 순서로 배열되어 있고 i번째 요소에 대한 검색 확률이 p_i일 때, 단일 검색의 예상 비용은 ES^{OPT} = \sum_{i=1}^n ip_i이다. 확률을 미리 알 수 없거나 확률에 따라 리스트를 정렬할 시간이 없다는 자연스러운 가정 하에, 자체 조정 데이터 구조 방식을 사용하여 검색에서 요청될 때 요소를 리스트의 맨 앞으로 이동시킬 수 있다. 이러한 자체 조정에 대한 두 가지 자연스러운 휴리스틱은 이동 전면(Move to Front, MF)과 전치(Transpose, T)이며, 요청된 요소는 그 선행 요소와 자리를 바꾼다. 독립적인 접근의 큰 시퀀스에서 접근의 예상 비용은 리스트의 모든 초기 순서에 대해 평균을 내면 ES^T \le ES^{MF} \le \frac{\pi}{2}ES^{OPT}를 만족하는 것으로 알려져 있다. 분할 상환 비용 측면에서, 최악의 연산 시퀀스에 대해 평균을 내면(확률에 대한 가정을 만족하는 시퀀스 중에서), S^{MF}\le 2S^{OPT}가 되는 반면, S^T는 O(mS^{OPT})만큼 나쁠 수 있다. isbn = 0849326494
# 응용
선형 검색은 일반적으로 구현이 매우 간단하며, 리스트에 요소가 몇 개 없거나 정렬되지 않은 리스트에서 단일 검색을 수행할 때 실용적이다. 같은 리스트에서 많은 값을 검색해야 할 때, 더 빠른 방법을 사용하기 위해 리스트를 전처리하는 것이 종종 이득이 된다. 예를 들어, 리스트를 정렬하고 이진 검색을 사용하거나, 효율적인 검색 자료 구조를 만들 수 있다. 리스트의 내용이 자주 변경되는 경우, 반복적인 재정렬은 그만한 가치가 없을 수도 있다. 결과적으로, 이론적으로 다른 검색 알고리즘이 선형 검색보다 빠를 수 있지만(예를 들어 이진 검색), 실제로는 중간 크기의 배열(100개 항목 이하)에서도 다른 것을 사용하는 것이 비실용적일 수 있다. 더 큰 배열에서는 데이터 정렬과 같은 초기 준비 시간이 많은 선형 검색과 비슷하기 때문에 데이터가 충분히 클 경우에만 다른, 더 빠른 검색 방법을 사용하는 것이 합리적이다.access-date=19 April 2013
# 소스 코드

## 파이썬
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; }
## 인용
각주
## 저서
* edition=2 위키데이터 속성 추적 분류:검색 알고리즘