검색 알고리즘

선형 검색(linear search): O(n)

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

int search(const int a[], int n, int key){
  int i;
  for(i=0;i<n;i++)
    if(a[i]==key) return i;
  return -1;
}

int main(void) {
  int i, nx, ky, idx;
  int *x;
  
  puts("선형 검색");
  printf("요소 개수: ");
  scanf("%d",&nx);
  x = calloc(nx, sizeof(int));
  for(i=0;i<nx;i++){
    printf("x[%d]: ",i);
    scanf("%d",&x[i]);
  }

  printf("검색값: ");
  scanf("%d",&ky);
  idx = search(x, nx, ky);
  if(idx==-1) puts("검색에 실패했습니다.");
  else printf("%d(은)는 x[%d]에 있습니다.\n",ky, idx);

  free(x);
  
  return 0;
}

 

• 보초법: 찾는 값을 배열 맨 끝에 저장 (저장하는 값을 '보초'라고 함)
  • 종료 판단 횟수를 2회에서 1회로 줄일 수 있음

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

int search(int a[], int n, int key){
  int i;
  a[n] = key;
  while(1) {
    if(a[i]==key) break;
    i++;
  }
  return i == n ? -1 : i;
}

int main(void) {
  int i, nx, ky, idx;
  int *x;
  
  puts("선형 검색(보초법)");
  printf("요소 개수: ");
  scanf("%d",&nx);
  x = calloc(nx+1, sizeof(int));
  for(i=0;i<nx;i++){
    printf("x[%d]: ",i);
    scanf("%d",&x[i]);
  }

  printf("검색값: ");
  scanf("%d",&ky);
  idx = search(x, nx, ky);
  if(idx==-1) puts("검색에 실패했습니다.");
  else printf("%d(은)는 x[%d]에 있습니다.\n",ky, idx);

  free(x);
  
  return 0;
}

---

이진 검색(binary search): O(log n)

배열이 정렬되어 있어야 함

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

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

int main(void) {
  int i, nx, ky, idx;
  int *x;
  
  puts("이진 검색");
  printf("요소 개수: ");
  scanf("%d",&nx);
  x = calloc(nx, sizeof(int));
  printf("오름차순으로 입력하세요.\n");
  for(i=0;i<nx;i++){
    printf("x[%d]: ",i);
    scanf("%d",&x[i]);
  }

  printf("검색값: ");
  scanf("%d",&ky);
  idx = bin_search(x, nx, ky);
  if(idx==-1) puts("검색에 실패했습니다.");
  else printf("%d(은)는 x[%d]에 있습니다.\n",ky, idx);

  free(x);
  
  return 0;
}

 

 

• bsearch 함수(정렬된 배열에서 검색하는 함수)
  • #include <stdlib.h>

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

int int_cmp(const int *a, const int *b){
  if(*a < *b) return -1;  //첫 번째가 작으면 음수
  else if (*a > *b) return 1; //첫 번째가 크면 양수
  else return 0;  //같으면 0
}

int main(void) {
  int i, nx, ky;
  int *x;
  int *p;
  
  puts("bseary 함수를 사용하여 검색");
  printf("요소 개수: ");
  scanf("%d",&nx);
  x = calloc(nx, sizeof(int));
  printf("오름차순으로 입력하세요.\n");
  for(i=0;i<nx;i++){
    printf("x[%d]: ",i);
    scanf("%d",&x[i]);
  }

  printf("검색값: ");
  scanf("%d",&ky);
  
  p = bsearch(&ky, x, nx, sizeof(int), // 키값 포인터, 배열 포인터, 요소 개수, 요소 크기
    (int(*)(const void *, const void *)) int_cmp); // 비교 함수, 호출 시 형변환을 하지 않아도 됨
  //p의 값은 '찾은 요소의 포인터'이므로 p-x로 인덱스를 얻을 수 있음
  if(p==NULL) puts("검색에 실패했습니다.");
  else printf("%d(은)는 x[%d]에 있습니다.\n",ky, (int)(p-x));

  free(x);
  
  return 0;
}

비교함수의 양수, 음수를 바꾸면 내림차순 배열에서 검색 가능