검색 프로그램

효율적인 검색 프로그램 만들기

아래 코드는 반복문을 통해 입력한 값이 검색될 때까지 반복하여 검색한다.

#include<stdio.h>

int main(){
    //무식한 검색 프로그램
    int num=0,ipt;
    int data[100];

    while(num<100){data[num]= num+ 1; num++;}

    printf("검색할 값을 입력하세요: "); scanf("%d",&ipt);

    for(int i=0;i<100;i++){ if(data[i]==ipt) {printf("찾으시는 값은 data 배열의 %d 번째에 있습니다.",i); break;}    }
    
}

반면 아래 코드는 사용자가 입력한 값과 배열을 분석하는 것이 큰 차이점인데, 배열의 중간값을 이용하여 대소 구분을 하고 대소구분 및 확인이 되었다면 비교할 공간의 크기를 변경하여 불필요한 반복을 줄일 수 있다.

 

하지만 아래의 코드가 사용되기 위해서 몇 가지 조건이 존재한다.

1. 값이 크기별로 정렬되어있어야 할 것,

2. 배열의 크기를 선언하거나 동적할당의 값을 알고 있어야 할 것.

3. 중복된 값이 없어야 할 것.

 

위의 조건을 충족한다면 배열의 검색에 있어 코드의 가독성은 떨어지는 면이 있으나 불필요한 메모리 소모를 줄일 수 있다.

#include <stdio.h>

int main() {
  //유식한 검색 프로그램
  int num = 0, ipt, index, rst;
  int data[100];

  int min = 0, max = 100;

  while (num < 100) {data[num] = num + 1;num++;}

  printf("검색할 값을 입력하세요: ");
  scanf("%d", &ipt);

  /*사용자가 입력한 값과 배열의 중간값을 비교하여 배열을 이등분한다.
  이때 베열의 중간값보다 작으면 배열의 앞부분과 비교, 크다면 배열의 뒷부분과
  비교한다.*/

  index = (max + min) / 2;
  while (max > min) {
    if (data[index] == ipt) {
      rst = index;
      break;
    } 
    else if (data[index] > ipt) { max = (max + min) / 2 - 1;}//배열의 중간값보다 작다면 다시 줄인 배열의 중간값과 비교
    else {min = (max + min) / 2 + 1;} //배열의 중간값보다 크다면
    index = (max + min) / 2;
  }
  printf("찾으시는 값은 data 배열의 %d 번째에 있습니다.", rst);
}

주의할 점

위의 코드는 메모리에 있어서 매우 효과적이나 알고리즘 상으로 주의해야 할 점이 있다.

...(생략)     else if (data[index] > ipt) { max = (max + min) / 2 - 1;}//배열의 중간값보다 작다면 다시 줄인 배열의 중간값과 비교     else {min = (max + min) / 2 + 1;} //배열의 중간값보다 크다면     index = (max + min) / 2;

max 값을 조건문 이후에 바꾸는 이유는 배열의 중간값보다 작으므로 다음 배열 비교 최대 인덱스 크기를 하나 낮춰줘야만 중복된 조건을 막을 수 있다. min 값을 바꾸는 이유도 동일한 이유이다.