이분 검색(Binary Search) - C언어/자료구조

'검색할 범위를 반으로 줄여가며 찾아가는 이분 검색(Binary Search)'

 

이분 검색은 검색할 자료를 반씩 나누어 나머지 반만 검색하는 방식을 반복하여

자료를 찾는 검색(탐색) 방법입니다.

 

이 이분 검색을 이용하여 자료를 찾는다면 빠른 속도로 원하는 자료를 찾을 수 있습니다.

(단, 이분 검색은 정렬되어있는 데이터에 사용할 수 있습니다.)

(정렬 방법은 블로그 내의 다른 글을 참고하시면 도움이 될 것 같습니다.)

 

 

성능을 Big O로 표기한다면

O(log n)입니다.

 자료가 2개라면 1번, 4개(2^2개)라면 2번, 8개(2^3개)라면 3번,

 16개(2^4개)라면 4번, ... 1,024개(2^10개)라면 10번,

 1,048,576개(2^19개)라면 최대 19번이면 찾습니다.

굉장히 빠르죠?

 

 

실제 배열에서 이분 검색(Binary Search)이 어떻게 되는지 확인해볼까요?

 

 

이분 검색은 위와 같이 정렬된 데이터를 가지고 검색해야 합니다!

 

 

 

이분 검색을 할 때는

찾고 싶은 데이터(키 값), 시작 위치에 대한 값,

종료 위치에 대한 값, 중간 위치에 대한 값이 필요합니다.

(키 값 외엔 모두 배열의 번호를 이야기 합니다.)

 

중간 위치를 찾을 때

(시작 위치 + 종료 위치) /2의 결과가 중간 위치 값이 됩니다.

 

이 중간 위치의 값을 키 값(찾을 데이터)과 비교하여

같다면 검색 종료, 작다면 왼쪽 데이터를 다시 검사, 크다면 오른쪽 데이터를 다시 검사하게 됩니다.

 

검색 종료가 되지 않았다면 다시 중간 위치를 찾고 데이터를 비교하는 과정을 반복합니다.

 

어떤 원리인지 아시겠나요?

 

이제 아래의 그림들로 정렬 과정을 보시죠.

(10개의 배열(0~9번) + 이분 검색으로 찾을 키 값은 6)

 

 

처음에는 중간 위치 값을 알아냅니다.

중간 위치는 (시작위치+종료위치)/2로 구할 수 있습니다.

(0+9)/2 = 4.5가 됩니다.

 

하지만 배열이기 때문에 정수로 사용합니다.

결과적으로 중간 위치 값은 4가 됩니다.

(정수로 형변환 시 소수점은 버림처리가 되죠?)

 

그리고 해당 중간 위치(4번 배열)의 데이터인 7과 키 값인 6을 비교합니다.

비교 결과 키 값이 더 작기 때문에, 더 검색을 진행합니다.

 

 

이제 검색 범위를 줄여야겠죠?

해당 데이터(4번 배열)와 (더 큰 데이터들이 있는)오른쪽의 값들은 검색에 필요 없기 때문에

종료 위치를 3으로 바꿔줍니다. (중간 위치-1)

이렇게 시작 위치는 0 그대로이고, 종료 위치가 3으로 바뀐 데이터를 가지고

다시 이분 검색(Binary Search)을 합니다.

 

이번에도 시작위치는 0이기 때문에

(0 + 3) / 2 = 1이 됐죠?

 

1번 배열의 데이터와 키 값을 비교한 결과

키 값인 6은 1번 배열의 데이터 3보다 크다는 결과가 나옵니다.

그렇다면 현재보다 우측에 원하는 값이 있다는 거겠죠?

 

아까와 달리 이번에는 우측을 찾으러 이동하기 때문에

시작 위치를 2로 바꿔줍니다. (중간 위치+1)

이제 둘 중 하나가 됐네요.

 

이렇게 시작 위치 2, 종료 위치 3인 상태에서

또 이분 검색을 진행합니다.

 

(2+3)/2 = 2가 됐죠?

 

2번 배열의 5와 키 값 6을 비교합니다.

비교 결과 키 값인 6이 2번 배열의 5보다 크다는 것을 알 수 있습니다.

 

 

또 시작 위치를 현재 중간 위치 +1인 3으로 바꿔줍니다.

(이제 시작 위치와 종료 위치가 같죠? 실질적으로 마지막 검사입니다.

만약 여기서도 같지 않다면, 그건 찾고 싶은 값의 데이터가 없다는 말이겠죠?)

자 이번에도 마찬가지로 시작 위치3, 종료 위치 3인 상태로

다시 이분 검색을 진행합니다.

 

(3+3)/2 = 3이 됐죠?

 

3번 배열의 6과 키 값인 6을 비교한 결과

같다는 것을 확인할 수 있습니다.

 

결과적으로 총 4번의 검사를 거쳐 데이터를 찾았습니다.

(10개의 데이터니 최대 4번 검사를 거치면 찾을 수 있는데, 최대치 만큼 확인했네요.

만약 찾고싶은 데이터가 7이였다면 한번에 찾았겠죠?)

(일반적인 선형 검색보다 훨씬 성능이 좋죠?)

 

 

그러면 한번만 더 확인해볼까요?

이번에는 길게 설명하지 않겠습니다.

 

앞의 검색 과정을 봤으니

이번에는 천천히 보면서 어떻게 진행될지 예측해보세요.

(0+9)/2 = 4

4번 배열(7) 키 값(9)를 비교한 결과

키 값이 4번 배열보다 크다는 것을 확인했습니다.

 

그렇다면 다음 검색 전 시작 위치가 0에서 5로 바뀌겠죠?

 

 

(5+9)/2 = 7

7번 배열(12) 키 값(9)를 비교한 결과

키 값이 7번 배열보다 작다는 것을 확인했습니다.

 

그렇다면 다음 검색 전 종료 위치가 9에서 6으로 바뀌겠죠?

 

 

(6+5)/2 = 5

5번 배열(9)와 키 값(9)를 비교한 결과

키 값이 5번 배열과 같은 값이라는 것을 확인했습니다.

 

그렇다면 이제 찾았기 때문에 검색은 종료되겠죠?

 

 

이분 검색(Binary Search) 어떻게 되는지 아시겠나요?

C언어나 사용하는 다른 프로그래밍 언어로 만들 수도 있겠나요?

 

 

 

 

 

그럼 이번에는 C 언어를 사용하여 이분 검색을 해볼까요?

(소스는 제공하지만, 위의 과정을 보고 직접 알고리즘, 소스를 만들어 보시면 좋을 것 같네요.)

 

 

출력 결과 예를 보고

프로그램의 소스를 작성해보세요.

 

(출력 결과 예)

 

 

 

 

제가 완성한 소스입니다.

 

 

보고 참고하세요.

(다른 방법으로도 만들 수 있겠죠?)

 

소스는 가장 기본형(목록에 없는 검사 확인 안 함),

없는 데이터인 경우가 추가 처리된 형태,

반복 횟수까지 측정하여 알려주는 형태

 

세 가지가 있습니다.

(모두 복사 가능하도록 올려뒀습니다.)

 

하나씩 확인해보고 어디가 어떻게 달라졌는지 확인해보세요.

 

 

 

 

 

//가장 기본형 (없는 데이터 입력하면 무한루프)

#include<stdio.h>
//Prosto
int main(void) {
 int data[10] = { 1, 3, 4, 6, 8, 10, 13, 14, 15, 16 }; //정렬된 데이터.
 int keyValue; //찾고 싶은 값.
 
 int startNum;
 int endNum;
 int midNum;
 while (1) { //무한 루프 계속 탐색을 위해.
  for (int i = 0; i < 10; i++) {
   printf("%d ", data[i]);
  }
  printf("\n어떤 값을 찾고싶나요?  : ");
  scanf_s("%d", &keyValue);
  //위는 검색 전 처리.
  startNum = 0;
  endNum = 9; //동적 할당 시엔 배열의 마지막 자리.
  while (1) { //찾을 때까지 무한루프..
   midNum = (startNum + endNum) / 2;
   if (data[midNum] < keyValue) {
    //키 값과 같은지 확인. 데이터가 더 작다면.
    startNum = midNum + 1;
   }else if (data[midNum] > keyValue) {
    //키 값과 같은지 확인. 데이터가 더 크다면.
    endNum = midNum - 1;
   }
   else { //키 값과 같다면.
    break;
   }
  }
  printf("Key값(%d)은 data[%d]에 있습니다.\n\n", keyValue, midNum);
 }
 return 0;
}

 

 

 

 

//없는 데이터도 확인하여 알려줌.

#include<stdio.h>
//Prosto
int main(void) {
 int data[10] = { 1, 3, 4, 6, 8, 10, 13, 14, 15, 16 }; //정렬된 데이터.
 int keyValue; //찾고 싶은 값.

 int startNum;
 int endNum;
 int midNum;
 while (1) { //무한 루프 계속 탐색을 위해.
  for (int i = 0; i < 10; i++) {
   printf("%d ", data[i]);
  }
  printf("\n어떤 값을 찾고싶나요?  : ");
  scanf_s("%d", &keyValue);
  //위는 검색 전 처리.
  startNum = 0;
  endNum = 9; //동적 할당 시엔 배열의 마지막 자리.
  while (1) { //찾을 때까지 무한루프..
   midNum = (startNum + endNum) / 2;
   if (startNum < endNum) { //(<인 이유는 같아지거나 반대가 되면 예외이기 때문)
    //마지막 검사 위치가 아니라면.
    if (data[midNum] < keyValue) {
     //키 값과 같은지 확인. 데이터가 더 작다면.
     startNum = midNum + 1;
    }
    else if (data[midNum] > keyValue) {
     //키 값과 같은지 확인. 데이터가 더 크다면.
     endNum = midNum - 1;
    }
    else { //키 값과 같다면.
     printf("Key값(%d)은 data[%d]에 있습니다.\n\n", keyValue, midNum);
     break;
    }
   }
   else { //마지막 검사위치에서는 따로.
    if (data[midNum] != keyValue) {
     //같지 않다면 존재하지 않는 데이터.
     printf("Key값(%d)은 data 배열에 존재하지 않습니다.\n\n", keyValue);
    }
    else { //키 값과 같다면.
     printf("Key값(%d)은 data[%d]에 있습니다.\n\n", keyValue, midNum);
    }
    break;
   }
  }
 }
 return 0;
}

 

 

 

 

 

 

//카운트까지.

#include<stdio.h>
//Prosto
int main(void) {
 int data[10] = { 1, 3, 4, 6, 8, 10, 13, 14, 15, 16 }; //정렬된 데이터.
 int keyValue; //찾고 싶은 값.

 int startNum;
 int endNum;
 int midNum;

 int count;
 while (1) { //무한 루프 계속 탐색을 위해.
  for (int i = 0; i < 10; i++) {
   printf("%d ", data[i]);
  }
  printf("\n어떤 값을 찾고싶나요?  : ");
  scanf_s("%d", &keyValue);
  //위는 검색 전 처리.
  startNum = 0;
  endNum = 9; //동적 할당 시엔 배열의 마지막 자리.
  count = 0;
  while (1) { //찾을 때까지 무한루프..
   count++;
   midNum = (startNum + endNum) / 2;
   if (startNum < endNum) { //(<인 이유는 같아지거나 반대가 되면 예외이기 때문)
    //마지막 검사 위치가 아니라면.
    if (data[midNum] < keyValue) {
     //키 값과 같은지 확인. 데이터가 더 작다면.
     startNum = midNum + 1;
    }
    else if (data[midNum] > keyValue) {
     //키 값과 같은지 확인. 데이터가 더 크다면.
     endNum = midNum - 1;
    }
    else { //키 값과 같다면.
     printf("[%d] Key값(%d)은 data[%d]에 있습니다.\n\n", count, keyValue, midNum);
     break;
    }
   }
   else { //마지막 검사위치에서는 따로.
    if (data[midNum] != keyValue) {
     //같지 않다면 존재하지 않는 데이터.
     printf("Key값(%d)은 data 배열에 존재하지 않습니다.\n\n", keyValue);
    }
    else { //키 값과 같다면.
     printf("[%d] Key값(%d)은 data[%d]에 있습니다.\n\n", count, keyValue, midNum);
    }
    break;
   }
  }
 }
 return 0;
} 

 

궁금한 점 있으시면 댓글이나 따로 메일로 질문하시면 시간되는 대로 답변드리겠습니다. ( 연락 )