C언어 이분탐색(Binary search)을 공부하자! - while문 활용

안녕하세요 판타지코딩월드입니다!

 

오늘은 C언어의 반복문을 구현할 때 활용하는 while문과 for문에 대해서 알아보고, while문을 활용하는 이분탐색(Binary search)에 대해서 공부해 보겠습니다.

 

반복문에는 for문과 while문이 있고, 이 두가지 문법은 저번시간에 공부했습니다. 때에 따라서 적절한 반복문을 선택하여 코드를 작성하면 됩니다. 그런데 for문은 반복 횟수를 정해놓는 코드가 기본이고, while문은 조건이 변함에 따라 반복 횟수가 변한다는 특성이 있습니다. 그래서 while문을 활용하여 이분탐색을 할 수 있습니다.

 

탐색이란?

이분탐색을 공부하기에 앞서, 탐색에 대해서 알아보겠습니다. 탐색은 보통 배열에서 특정 데이터가 존재하는지 여부를 확인할 때 하는 것입니다. 예를 들어, 배열 arr에 숫자 '3'이 존재하는지 확인하는 코드가 있다면, 0번째부터 숫자 '3'이 존재하는 위치까지 하나씩 탐색하는 방법이 있습니다.

 

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for(int i=0; i<10; i++)
{
    if(arr[i] == 3)
    {
        printf("3을 찾았다!");
        break;
    }
}

 

코드는 이렇게 for문을 활용해서 구현할 수 있습니다. 배열 arr에 1부터 10까지 10개의 데이터가 저장되어 있고, 3을 찾기 위해서 for문을 활용해서 0번째부터 확인합니다. i가 0일 때 arr[0]은 1, i가 1일 때 2 이렇게 찾다보면 i가 2인 세 번째 위치에서 '3'을 찾을 수 있습니다. 그럼 "3을 찾았다!"를 출력하고 break;로 for문을 중단합니다.

 

이분탐색을 활용하는 이유

이처럼 특정 데이터를 찾는 과정을 '탐색'이라고 합니다. 그런데 이 탐색 과정이 길어질 때 시간 초과라는 문제가 생길 수 있습니다. 위에서는 '3'을 찾기 때문에 세 번 만에 끝났지만, 만약 '9'를 찾는다면 어떨까요? 물론 9번이면 끝납니다. 하지만, 배열이 100개, 1000개가 넘어갈 경우 뒤에 있는 수를 찾을수록 더 많은 시간이 소요됩니다. 이럴때 활용할 수 있는 방법이 '이분탐색'입니다!

 

이분탐색

드디어 이분탐색에 대해 공부할 차례가 왔습니다! 이분탐색은 단어처럼 반으로 나누어서 탐색을 하는 과정입니다. 그래서 탐색 횟수도 반으로 줄여나가면서 할 수 있습니다. 예를 들어 숫자 1부터 8까지를 저장한 배열 arr에서 '2'을 찾아보겠습니다. 그런데 이번에는 0번째부터 탐색하지 않고, 중간값부터 탐색을 시작하겠습니다. 이 중간값은 첫 번째 위치와 마지막 위치의 평균을 구해서 얻은 값입니다. 이 값을 arr[mid] 로 작성해서 arr의 중간에 있는 값을 구하는 것입니다.

이분 탐색(Binary search) 자료

가장 앞쪽 0번째를 'start', 가장 마지막인 7번째를 'end'로 변수를 생성할 수 있습니다. 그리고 이 값의 평균값인 3이 바로 'mid'가 됩니다. 'mid'는 (start+end)/2로 구할 수 있습니다. 그럼 arr[mid]인 arr[3]은 '4'인 것을 확인할 수 있습니다. '4'는 우리가 찾는 값인 '2'보다 크므로 mid값을 줄여야 함을 알 수 있습니다. 그러므로 end값을 mid보다 작은 값인 mid-1 = 2로 변경합니다. 이렇게 되면, '4'이상인 값 5, 6, 7, 8은 탐색 대상에서 제외되므로 범위가 반으로 줄어들게 됩니다. 이런식으로 찾는 값보다 arr[mid]값이 작은지 큰지를 판단해서 start와 end값을 조정해 mid값을 구해서 arr[mid]값을 판단하면 됩니다.

 

int arr[8] = {1, 2, 3, 4, 5, 6, 7, 8];

int st = 0;
int ed = 7;
int mid;

while(st<=ed)
{
    mid = (st+end)/2;
    if(arr[mid]<=2)
    {
        if(arr[mid]==2)
        {
            printf("2를 찾았다!");
            break;
        }
        ed = mid - 1;
    }
    else
    {
        st = mid + 1;
    }
}

 

이분탐색을 코드로 이렇게 구현할 수 있습니다. while문의 조건으로 st<=ed일 동안 반복되도록 했습니다. st와 ed값을 조정하면서 코드가 반복되는데, 이 때 st값이 ed값을 넘어가면 코드가 무한히 반복되므로 이러한 조건을 작성한 것입니다. 또한 st값은 배열의 앞쪽, ed값은 뒷쪽을 의미하는데, 이렇게 앞쪽과 뒷쪽을 나눠서 탐색 범위를 줄여나가는 것인데 이 값의 순서가 바뀌면 또 다시 같은 곳을 탐색하게 될 것입니다.

 

arr[mid]가 찾는 값과 같다면 "2를 찾았다!"를 출력하고 반복문을 중단합니다. 만약 더 크다면 mid값을 줄이기 위해 ed = mid-1로 변경합니다. 그리고 arr[mid]가 찾는 값보다 작다면, 더 큰 숫자를 탐색해야 하므로 mid값을 증가시키면 되므로 st = mid+1로 변경해서 다시 탐색합니다. st와 ed값을 변경하는 과정에서 범위가 어떻게 줄어드는지를 중심으로 공부하시면 되겠습니다.

 

그럼 오늘은 while문을 활용한 '이분 탐색(Binary search)'에 대해서 공부해 보았습니다. start값과 end 값으로 mid값을 생성할 때 어떻게 범위가 바뀌는지를 이해하셨다면 오늘은 100점입니다!

 

감사합니다!