[자료구조와 함께 배우는 알고리즘 입문 - C언어 편] 3장 검색 연습문제 Q5 답안 p.115

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

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

---

답안)

#include <stdio.h>
#include <stdlib.h>

int bin_search2(const int a[], int n, int key) {
  int j;
  int pl = 0;
  int pr = n-1;
  int pc;
  int chk = 1;
  do {
    pc = (pl + pr) / 2;
    if(a[pc] == key)
      chk = 0;
    else if(a[pc] < key)
      pl = pc + 1;
    else
      pr = pc - 1;
  } while(chk);

  for(j=1; j<pc; j++) {
    if (a[pc-j] != key)
      return pc-j+1;
  }
  return -1;
}

int main(void) {
  int i, nx, ky, idx;
  int *x;
  puts("이진 검색");
  printf("요소 개수 : ");
  scanf("%d", &nx);
  x = calloc(nx, sizeof(int));
  printf("오름차순으로 입력하세요.\n");
  printf("x[0] : ");
  scanf("%d", &x[0]);
  for(i=1; i<nx; i++) {
    do {
      printf("x[%d] : ", i);
      scanf("%d", &x[i]);
    } while(x[i] < x[i-1]);
  }
  printf("검색값 : ");
  scanf("%d", &ky);
  idx = bin_search2(x, nx, ky);
  if(idx == -1)
    puts("검색에 실패했습니다.");
  else
    printf("%d는(은) x[%d]에 있습니다.\n", ky, idx);
  free(x);
  return 0;
}

---

실행 결과)

sy@sy:~/algorithm/doit/chap03$ gcc bin_search2.c -o bin_search2
sy@sy:~/algorithm/doit/chap03$ ./bin_search2
이진 검색
요소 개수 : 11
오름차순으로 입력하세요.
x[0] : 1
x[1] : 3
x[2] : 5
x[3] : 7
x[4] : 7
x[5] : 7
x[6] : 7
x[7] : 8
x[8] : 8
x[9] : 9
x[10] : 9
검색값 : 7
7는(은) x[3]에 있습니다.

블로그를 바꿔야겠네요.. 글 쓰는게 너무 불편하네..