백준 알고리즘 #2 - 이진 탐색

이번 포스트에서는 이진탐색(Binary search)에 대해 알아보겠습니다.

이진탐색은 빠른 탐색 알고리즘에 속합니다.

for문을 돌려 순회하는 방식은 배열 전체를 돌아야 하기 때문에 시간복잡도 O(N)을 가지지만,  탐색 구간을 계속 반으로 줄여나가는 이진탐색은 시간복잡도 O(logN)을 가집니다.

 

 

 

🏳️ 이진 탐색을 위해 준비해야 할 것은?

 - 먼저 이진탐색을 하기 위해서는 정렬이 먼저 되어있어야 합니다. (알고리즘 #1 - qsort를 참고해 주세요)

 

 

 

🏳️ 이진 탐색의 원리

 - 이진 탐색은 배열 안에서 원하는 값을 찾기 위해 탐색 구간을 계속 반으로 줄여 나갑니다.

 

    ex) 배열의 원소가 {4, 2, 5, 1, 13, 8, 7}이고 찾으려는 원소가 '2' 일 때

 

   

 

STEP1) 배열을 정렬합니다.

 

 

 

 

 

 

STEP2) 시작 위치, 중간 위치, 끝나는 위치, KEY의 위치를 정해줍니다.

 

 

 

 

   

 

 

STEP3) 만약 중간위치의 값이 없다면 시작위치 혹은 끝나는 위치 위치의 값을 바꿔줍니다.

 

이때의 경우에는 KEY값이 CENTER가 가리키는 값보다 더 크기 때문에 START~CENTER 구간 사이에는 원하는 KEY가  없습니다.

그렇기 때문에 START라인을 직전 CENTER 바로 뒤로 옮겨줍니다. 다음으로 CENTER의 위치를 재설정

해줍니다. (만약 KEY값이 CENTER가 가리키는 값보다 작으면 END를 CEN 앞쪽으로 옮겨주면 됩니다.) 

 

 

   

 

STEP4) CENTER의 값과 KEY의 값이 일치함으로 원하는 KEY가 배열에 존재한다는 걸 알 수 있습니다.

또한, CENTER의 위치를 통해 KEY값이 위치하는 INDEX도 알 수 있습니다.

 

   

이를 코드로 나타내면 다음과 같습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int compare(const void* num1, const void* num2)
{
	int a = *(int*)num1;
	int b = *(int*)num2;

	if (a > b)
	{
		return 1;
	}
	else if (a < b)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int search(int* ary, int size, int key)
{
	int start = 0, end = size - 1;
	while (start <= end) // start값이 end보다 작거나 같을때 까지 반복문을 돌린다.
	{
		int cen = (start + end) / 2;
		
		if (ary[cen] == key)
		{
			return cen; // key가 배열안에 존재할 때
		}
		else if (ary[cen] > key)
		{
			end = cen - 1;  
		}
		else if (ary[cen] < key)
		{
			start = cen + 1; 
		}
	}
	return -1; // key가 배열안에 존재하지 않을 때 
}


int main(void)
{
	int ary[7] = { 4, 2, 1, 5, 13, 8, 7 };
	int key = 2;
	qsort(ary, 7, sizeof(int), compare);
	int result = search(ary, 7, 2);
	if (result == -1)
	{
		printf("원하는 KEY가 배열안에 존재하지않습니다.");
	}
	else
	{
		printf("원하는 KEY가 배열안에 존재합니다.");
	}
}

            

 

 

 

🏴 심화 - Lower bound(하한)과 Upper bound(상한)

 - 이진 탐색을 구현하다 보면 어떤 KEY가 배열 안에 중복으로 존재하고, 그 KEY가 어느 구간부터 어느 구간까지 존재하는지 알아야 하는 경우가 있습니다.

아래의 경우가 그 예시입니다.

 

이때,  이진 탐색의 하한과 상한을 통해 배열에 존재하는 KEY의 시작 위치(인덱스)와 마지막 위치(인덱스)를 알 수 있습니다.

 

 

 

 

🏴 Lower bound(하한)

 - 배열의 원소가 {1, 2, 2, 3, 3, 3, 7}이고 찾으려는 원소가 '3' 일 때를 예시로 들어보겠습니다.

 

 

 

STEP1) 초기 위치, 중간 위치, 마지막 위치와 KEY값을 업데이트해 줍니다.

 

 

 

 

 

STEP2) 만약 중간값이 KEY보다 크거나 같으면 끝나는 위치를 CEN으로 조정해 줍니다.

             혹은, 중간값이 KEY보다 작으면 초기 위치를 CEN + 1로 조정해 줍니다. 

 

 

 

 

 

 

 

STEP3) 끝나는 위치가 시작 위치가 같거나 작을 때, 이진탐색은 끝이 나게 됩니다.

이때, END값은 '3'이 처음 등장하는 INDEX인 3을 가리킵니다.

 

 

 

 

즉, '3' 이상인 값은 INDEX가 3인 곳부터 시작하게 됩니다.

이를 코드로 나타내면 다음과 같습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int lower_bound (int* ary, int size, int key)
{
    int start = 0, end = size - 1;
    while (start < end)
    {
        int cen = (start + end) / 2;
        if (ary[cen] >= key)
        {
            end = cen;
        }
        else
        {
            start = cen + 1;
        }
    }
    return end;
}


int main() 
{
    int ary[7] = { 1, 2, 2, 3, 3, 3, 7 };
    int key = 3;
    int result = lower_bound(ary, 7, 3);

    if (result != 7) 
    {
        // 값을 찾은 경우
        printf("3이상인 값은 %d 위치에서 시작합니다.", result);
    }
    else 
    {
        // 값을 찾지 못한 경우
        printf("찾지못했습니다.");
    }
}

 

만약, '8' 같이 배열의 가장 큰 수보다 큰 숫자가 들어오면 마지막 위치를 배열의 크기로 설정하고 반환하기 때문에 출력 시 예외를 따져 주어야 합니다.

 

 

🏴 Upper bound(상한)

 - 위와 같이 배열의 원소가 {1, 2, 2, 3, 3, 3, 7}이고 찾으려는 원소가 '3' 일 때를 예시로 들어보겠습니다.

 

 

 

STEP1) 초기 위치, 중간 위치, 마지막 위치와 KEY값을 업데이트해 줍니다.

 

 

 

 

 

STEP2) 만약 중간값이 KEY보다 크다면 끝나는 위치를 CEN으로 조정해 줍니다.

             혹은, 중간값이 KEY보다 작거나 같으면 초기 위치를 CEN + 1로 조정해 줍니다. 

 

 

 

 

 

 

STEP3) 끝나는 위치가 시작 위치가 같거나 작을 때, 이진탐색은 끝이 나게 됩니다.

이때, END값은 '3'을 처음 초과하는 INDEX인 6을 가리킵니다.

 

 

 

즉, '3' 초과인 값은 INDEX가 7인 곳부터 시작하게 됩니다.

이를 코드로 나타내면 다음과 같습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int upper_bound (int* ary, int size, int key)
{
    int start = 0, end = size - 1;
    while (start < end)
    {
        int cen = (start + end) / 2;
        if (ary[cen] > key)
        {
            end = cen;
        }
        else
        {
            start = cen + 1;
        }
    }
        return end;
}


int main() 
{
    int ary[7] = { 1, 2, 2, 3, 3, 3, 7 };
    int key = 3;
    int result = upper_bound(ary, 7, 3);

    if (result != 7) 
    {
        // 값을 찾은 경우
        printf("3을 초과하는 값은 %d 위치에서 시작합니다.", result);
    }
    else 
    {
        // 값을 찾지 못한 경우
        printf("찾지못했습니다.");
    }
}

 

Lower bound의 값은 3입니다. 또한 Upper bound의 값은 6입니다.

즉, Upper bound(처음으로 초과하는 위치) - Lower bound(처음으로 등장하는 위치) = 3이며,

결론적으로 '3'는 배열에 '3'개 존재한다는 것을 알 수 있습니다.

만약, KEY가 '4'일 경우일 땐 Lower bound = 6, Upper bound =6이므로 6 - 6 = 0입니다.

고로 '4'는 배열에 '0'개 존재한다는 걸 알 수 있습니다.