개발자의 C언어 독학 기초 # 응용 / 2진탐색

개발자의 C언어 독학 기초 # 응용 / 2진탐색

모든 강의 자료 : www.codingnow.co.kr/

2진 탐색은 찾고자 하는 값이 어디에 있는지 찾는 알고리즘 중에 하나이다.

​

검색 자료의 중간을 찾아 중간의 값과 비교하여 같으면 종료 그 중간값이 작으면 위로 크면 아래로 이것을 계속적으로 반복해서 찾는 알고리즘이다.

​

반드시 알고리즘 특성상 정렬이 된 DB에서만 가능하다.

 

#include <stdio.h>
#include <windows.h> //system 명령 실행을 위해


int TargetArr[10] = {1,2,4,6,8,13,14,16,18,19};
	
int SearchIndex(int target)
{
  int low,high,mid;	
  low = 0; //TargetArr 첫번째값 
  high = 10; //TargetArr 마지막값

  while(1){
    if(low<=high){
      mid=(low+high)/2; //mid값 계산 (소수점이하는 자동으로 절삭)

      if(target==TargetArr[mid]){
        printf("\n %d는 %d번째 있습니다.",target,mid);
        break;
      }

      printf(" (%d,%d,%d)\n",low,mid,high);
      if(target<=TargetArr[mid]){
          high=mid; //mid값 위 절삭 
      }else{
          low=mid; //mid값 아래 절삭
      }

      if(mid == 0 || mid >= 9)
      {
        printf("\n %d는 존재하지 않습니다.",target);
        break;				
      }
    }else{
      printf("\n %d는 존재하지 않습니다.",target);
      break;
    }
  }
}

void main(void)
{
  system("chcp 65001"); //gcc 한글 깨짐
  system("cls"); //화면지움

  int target;

  printf("\n검색 배열 값 : ");
  for (int i = 0; i < 10; i++)
  {
  	printf("%d ", TargetArr[i]);
  }
  printf("\n\n 찾고자 하는 수의 index를 입력하세요 : ");
  scanf("%d",&target);


  SearchIndex(target);//검색 함수 호출

  printf("\n\n");

  return;
}

​