Page 98 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

03-2 선형 검색

이번 절에서는 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘을 살펴보겠습니다.
이 알고리즘은 선형 검색(linear search)이라고 하며 다음 장에서도 자주 사용하므로 확실히 익
혀 두어야 합니다.

선형 검색

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨
앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색
(sequential search)이라는 알고리즘입니다. 구체적인 과정을 아래의 데이터 나열을 예로 들어
살펴보겠습니다.

０ １ ２ ３ ４ ５ ６
6 4 3 2 1 3 8

이 배열에서 값 2의 요소를 선형 검색하는 모습이 그림 3-2입니다.

１ ２ ３ ４ ５ ６
a 6 4 3 2 1 3 8
０ ❶ ２ ３ ４ ５ ６
b 6 4 3 2 1 3 8
배열의 요소를 맨 앞부터
０ １ ❷ ３ ４ ５ ６ 순서대로 검색합니다.
c 6 4 3 2 1 3 8

０ １ ２ ❸ ４ ５ ６
d 6 4 3 2 1 3 8

검색 성공!
검색할 값과 같은 요소를 발견
[그림 3-2] 선형 검색의 예(2를 검색 : 검색 성공)

이 그림에서 ● 안의 값은 배열 요소의 인덱스입니다. 검색은 다음과 같이 진행됩니다.

98 C 알고리즘