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

Q1 실습 3-3의 search 함수를 while문이 아니라 for문을 사용하여 수정한 프로그램을 작성
연습
문제 하세요.

Q2 오른쪽처럼 선형 검색의 스캐닝 과정을 상세하게 표시 | 0 1 2 3 4 5 6
---+------------------------------
하는 프로그램을 작성하세요. 이때 각 행의 맨 왼쪽에 현재 검 | *
0 | 6 4 3 2 1 9 8
색하는 요소의 인덱스를 표시하고, 현재 검색하고 있는 요소 |
| *
위에 별표 기호 *를 표시하세요. 1 | 6 4 3 2 1 9 8
|
| *
2 | 6 4 3 2 1 9 8
3은 x[2]에 존재합니다.

이진 검색의 시간 복잡도
이진 검색법을 이용하면 검색할 요소의 범위를 절반씩 줄일 수 있습니다. 프로그램 각 단계의
실행 횟수와 복잡도는 표 3-2와 같습니다.

int bin_search(const int a[], int n, int key)
{
1 int pl = 0; /* 검색 범위 맨 앞의 인덱스 */
2 int pr = n – 1; /* 검색 범위 맨 끝의 인덱스 */

do {
3 int pc = (pl + pr) / 2; /* 중앙 요소의 인덱스 */
4 if(a[pc] == key)
5 return pc; /* 검색 성공 */
6 else if(a[pc] < key)
7 pl = pc + 1; /* 검색 범위를 뒤쪽 반으로 줄임 */
8 else
9 pr = pc – 1; /* 검색 범위를 앞쪽 반으로 줄임 */
10 } while(pl <= pr);

11 return –1; /* 검색 실패 */
}

이 프로그램은 실습 3-4의 bin_search 함수를 수정한 코드입니다.

03•검색 113