(C언어) 6. 이진탐색

<이진 탐색>

1. 개요

 처음 이진 탐색이라는 것을 보자마자 난 이런 생각을 했다.

"이진 탐색? 이진수로 파일을 탐색하는건가?"

 이렇게 생각하며 겁먹었다.

 하지만 검색을 하고 온 결과 별거 아니라는 걸 알게 되었고, 프로그래밍 수업시간에 이중for문과 랜덤함수를 이용해서 재미로 숫자맞추기 게임을 만들었었는데 그거랑 비슷하다는 것을 또 알았다.

2. 이진 탐색의 정의

네이버 지식백과에선 이렇게 써있다.

이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법이다.

쉽게 설명하자면 이런거다 : (단, 중앙에 있는 값을 찾는 알고리즘은 (범위에서의 최대값+범위에서의 최솟값-1)/2 이다.)

1~100까지의 수 중에서 97이라는 수를 이진 탐색으로 찾고싶어졌다.

<1: 1~100에서 정확히 중앙에 있는 값을 기준으로 큰가? 작은가(작거나 같은가)?를 판단한다.

중앙의 값 : (100+1-1)/2=50

당연히 97은 50보다 크다. 따라서 현재의 범위는 50<97<=100이다.

<2: 51~100에서 정확히 중앙에 있는 값을 기준으로 큰가? 작은가(작거나 같은가)?를 판단한다.

중앙의 값 : (100+51-1)/2=75

당연히 97은 75보다 크다. 따라서 현재의 범위는 75<97<=100이다.

<3: 76~100에서 정확히 중앙에 있는 값을 기준으로 큰가? 작은가(작거나 같은가)?를 판단한다.

중앙의 값 : (100+76-1)/2=87.5=87 (C언어에선 int 형으로 변수를 선언 했을 때 0.5를 버림함.)

당연히 97은 87보다 크다. 따라서 현재의 범위는 87<97<=100이다.

<4: 88~100에서 정확히 중앙에 있는 값을 기준으로 큰가? 작은가(작거나 같은가)?를 판단한다.

중앙의 값 : (100+88-1)/2=91.5=91

당연히 97은 91보다 크다. 따라서 현재의 범위는 91<97<=100이다.

<5: 92~100에서 정확히 중앙에 있는 값을 기준으로 큰가? 작은가(작거나 같은가)?를 판단한다.

중앙의 값 : (100+92-1)/2=95.5=95

당연히 97은 95보다 크다. 따라서 현재의 범위는 95<97<=100이다.

<6: 96~100에서 정확히 중앙에 있는 값을 기준으로 큰가? 작은가(작거나 같은가)?를 판단한다.

중앙의 값 : (100+96-1)/2=97.5=97

중앙의 값과 찾고 싶은 값이 97로 일치한다. 프로그램을 종료한다.

 즉, 정리하자면

1. 배열을 작은거부터 큰거 순서대로 쭉 나열한다.

2. 절반 나눠서 대소 여부 판단. "중앙값==찾고싶은 값"일때까지 무한루프.

3. 코드

그럼 코드를 하나 보자.

#include <stdio.h>
 
int main(){
    int arr[100];
    int input;
    int i, j;
    int userwant;
    int temp;
    int first, middle, last;//최솟값, 중앙값, 최댓값
    int howmany=0;
 
    printf("입력받을 숫자의 개수 : ");
    scanf("%d", &input);
 
    printf("공백으로 구분하며 값을 입력하세요\n");
    for (i = 0; i < input; ++i){
        scanf("%d", &arr[i]);
    }
 
    for (i = 0; i < input - 1; ++i) {//숫자 정렬
        for (j = 0; j < input - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
 
    printf("찾고자 하는 값은 : ");
    scanf("%d", &userwant);
 
    first = 0;
    last = input - 1;
    while(1){
        middle = (arr[first] + arr[last] - 1) / 2;
        if (userwant == arr[middle]) {
            break;
        }
        else if(userwant<arr[middle]){
            last = middle - 1;
            ++howmany;
        }
        else if(userwant>arr[middle]){
            first = middle + 1;
            ++howmany;
        }
    }
    
    printf("당신이 찾고자 한 값을 binary search를 이용해서 %d번만에 찾았습니다\n", howmany);
}

코드 20번째 줄~28번째 줄은 숫자를 정렬하는 알고리즘이 들어있다.

코드 33~48줄에는 binary search를 이용한 숫자 찾기 알고리즘이 들어있다.

여기서 howmany 변수는 이 무한루프가 몇 번 돌았는지를 알려주는 변수이다.

나머지는 변수 명과 주석으로 충분히 설명 되리라 믿는다.