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

원래 데이터 보초
a 2를 검색(검색 성공)
０ １ ２ ❸ ４ ５ ６ ７
6 4 3 2 1 3 8 2
검색할 값과 같은 요소를 발견
b 5를 검색(검색 실패)
０ １ ２ ３ ４ ５ ６ ❼
6 4 3 2 1 3 8 5
검색할 값과 같은 요소를 발견
※ 단 발견한 것은 보초
[그림 3-4] 보초법을 이용한 선형 검색

이 그림에서 배열의 요소 a[0] ~ a[6]은 초기에 준비해 놓은 데이터입니다. 검색하기 전에 검

색하고자 하는 키 값을 맨 끝 요소 a[7]에 저장합니다. 이때 저장하는 값을 보초(sentinel)라고
합니다.

a : 2를 검색하기 위해 보초로 a[7]에 2를 저장합니다.
b : 5를 검색하기 위해 보초로 a[7]에 5를 저장합니다.

그러면 b 처럼 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 a[7]까지 검색하면 종료
조건 ②가 성립합니다. 이렇게 하면 원하는 키 값을 찾지 못 했을 때 종료 조건 ①이 없어도 됩

니다. 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 합니다. 이런 보초법
을 도입하여 실습 3-1을 수정한 프로그램이 실습 3-3입니다. 회색으로 표시한 부분에서는
입력한 요소 개수에 1을 더한 크기의 배열을 생성합니다.
요소 개수로 7이 입력되면 요소 개수가 8인 배열을 생성합니다. 본래의 데이터에 보초의 자리를 추가하기 위해서입니다.

search 함수를 먼저 설명하고 그 다음에 실습 3-3의 나머지 코드를 설명하겠습니다.

실습 3-3 •완성 파일 chap03/ssearch_sen.c

01 /* 선형 검색(보초법) */
02 #include <stdio.h>
03 #include <stdlib.h>
04
05 /*--- 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법) ---*/
06 int search(int a[], int n, int key)

03•검색 103