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

34 puts("검색에 실패했습니다.");
35 else
36 printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
37 free(x); /* 배열 해제 */
38
39 return 0;
40 }

search 함수는 배열 a의 처음부터 끝까지 n개의 요소를 대상으로 값이 key인 요소를 선형 검
색합니다. 반환값은 발견한 요소의 인덱스입니다. 또한 값이 key인 요소가 여러 개 존재한다
면 반환값은 검색 과정에서 처음 발견한 요소의 인덱스가 됩니다. 값이 key인 요소가 존재하

지 않으면 –1을 반환합니다.
3을 검색하면 이 값은 배열의 x[2]와 x[5]의 두 곳에 존재하지만 가장 먼저 찾은 x[2]의 인덱스 값인 2를 반환합니다.

배열을 검색할 때 배열 요소의 인덱스를 가리키는 변수는 i입니다. i는 0으로 초기화하고 요
소를 하나 검색할 때마다 while문이 제어하는 루프 본문의 끝에서 증가시킵니다. while문

을 빠져나가는 경우는 앞에서 살펴본 종료 조건 가운데 하나가 성립한 경우입니다.

1 i == n이 성립하는 경우 (종료 조건 ① : 검색 실패이므로 –1을 반환)
2 a[i] == key가 성립하는 경우 (종료 조건 ② : 검색 성공이므로 i를 반환)

while문을 반복할 때 계속해서 실행할지에 대한 판단은 회색으로 표시한 부분의 ‘1’로 평가합니다(계속 반복하기 위해 의
도적으로 넣은 값입니다). 따라서 조건 판단 횟수는 2회가 아니라 3회(while(1), if(i == n), if(a[i] == key))입니다.

이때 배열의 검색을 while문이 아니라 for문으로 구현하면 프로그램은 보다 짧고 간결해집
니다. 다음의 실습 3-2는 while문을 for문으로 수정한 프로그램입니다.

실습 3-2 •완성 파일 chap03/ssearch2.c
01 /*--- 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색(버전 2 : for문) ---*/
02 int search(const int a[], int n, int key)
03 {
04 int i;
05 for(i = 0; i < n; i++)
06 if(a[i] == key)
07 return i; /* 검색 성공 */
08 return –1; /* 검색 실패 */
09 }

처음부터 순서대로 요소를 검사하는 선형 검색은 임의로 늘어놓은 배열에서 검색하는 방법 중 유일한 방법입니다.
03•검색 101