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

03-1 검색 알고리즘

이 장에서는 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해 살펴
보겠습니다.

검색과 키
주소록을 검색한다고 가정해 보겠습니다. 한 마디로 검색(searching)이라고 표현은 하지만 실

제로 검색 과정은 아래와 같은 방법으로 이루어집니다.

1. 국적이 일본인 사람을 찾는다.
2. 나이가 21세 이상 27세 미만인 사람을 찾는다.
3. 어떤 낱말과 발음이 가장 비슷한 이름의 사람을 찾는다.

위의 검색뿐만 아니라 어떤 검색을 하게 되더라도 특정 항목에 주목한다는 점은 ‘검색하기’의

공통점입니다. 여기서는 그 주목하는 항목을 키(key)라고 하겠습니다. 국적을 검색하는 경우
국적이 키이고 나이를 검색하는 경우 나이가 키입니다. 데이터가 단순한 정수 값이면 데이터
값을 키 값이라고 생각해도 좋지만 대부분의 경우에서 키는 데이터의 ‘일부’입니다. 그런데

위의 검색 과정을 살펴보면 키 값을 아래처럼 지정하고 있습니다.

1. 키 값과 일치하도록 지정합니다(한국).
2. 키 값의 구간을 지정합니다(21세 이상 27세 미만).
3. 키 값과 비슷하도록 지정합니다(발음이 가장 비슷한 이름).

물론 이런 조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용하여 복합해서 지정

하기도 합니다.

배열에서 검색하기

그림 3-1은 검색에 대한 세 가지 예로, 이 세 가지 검색 기법에서 몇몇은 자료구조에 의존하

03•검색 95