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

연습 Q3 요소의 개수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부
문제 터 순서대로 저장하고, 일치한 요소의 개수를 반환하는 함수를 작성하세요. 예를 들어, 요소의 개
수가 8인 배열 a의 요소가 {1, 9, 2, 9, 4, 6, 7, 9}이고 key가 9면 배열 idx에 {1, 3, 7}을 저장하
고 3을 반환합니다.

int search_idx(const int a[], int n, int key, int idx[]);

Q4 오른쪽처럼 이진 검색의 과정을 자세히 출력하는 프로 | 0 1 2 3 4 5 6
---+------------------------------
그램을 작성하세요. 각 행의 맨 왼쪽에 현재 검색하고 있는 요 | <- + ->
3 | 1 2 3 5 6 8 9
소의 인덱스를 출력하고, 검색 범위의 맨 앞 요소 위에 <-, 맨 |
| <- + ->
끝 요소 위에 ->, 현재 검색하고 있는 중앙 요소 위에 +를 출력 1 | 1 2 3 5 6 8 9
하세요. 2는 x[1]에 있습니다.

Q5 우리가 살펴본 이진 검색 알고리즘 프로그램은 검색할 값과 같은 값을 갖는 요소가 하나 이
상일 경우 그 요소 중에서 맨 앞의 요소를 찾지 못합니다. 예를 들어, 아래 그림의 배열에서 7을 검
색하면 중앙에 위치하는 a[5]를 검색합니다. 맨 앞의 요소를 찾는 bin_search2 함수를 작성해
보세요.

int bin_search2(const int a[], int n, int key);

이진 검색 알고리즘에 의해 검색에 성공했을 때( a ) 그 위치로부터 앞쪽으로 하나씩 검사하면( b ) 여러 요
소가 일치하는 경우에도 가장 앞쪽에 위치하는 요소의 인덱스를 찾아냅니다

０ １ ２ ３ ４ ❺ ６ ７ ８ ９ １０
a 1 3 5 7 7 7 7 8 8 9 9

0 1 2 ❸ 4 ❺ 6 7 8 9 １０
b 1 3 5 7 7 7 7 8 8 9 9
배열의 맨 앞을 넘지 않는 범위에서 같은 값의 요소가 계속되는 한 앞쪽으로 스캔합니다.

03•검색 115