하한(Lower bound), 상한(Upper bound)

하한, 상한은 배열이 이미 정렬된 상태에서 적용되어야합니다. 상한, 하한은 모두 이진 탐색(Binary Search)로 구현이 되어있기 때문이죠. 여기서 이진 탐색은 아래의 코드인 것을 알고 계시겠죠? 이진 탐색의 기본 코드는 아래와 같습니다. 이진 탐색의 탐색 속도는 O(lg 2)의 속도를 자랑하지요. 

 

 

int BinarySearch(int s, int e, int number)
{
    int left=s,right=e,mid;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] == number) return mid;
        if (arr[mid] > n) right = mid -1;
        else left = mid + 1;
    }
    return -1;
}

 

하한이란? (Lower Bound)

특정 값 K보다 같거나 큰 값이 처음 나오는 위치가 됩니다. 즉, K값 이상인 값이 맨 처음 나오는 위치여야합니다. 아래는 그 예를 나타내는 표입니다. 이때 맨 앞 요소의 index는 0으로 시작합니다.

배열
1 2 2 4 4 5 6 6 6 9 9
lower_bound
lower bound( 4 )  3
lower bound( 5 )  5
lower bound( 9 )  9

하한을 Binary Search방식으로 구현한 코드는 아래와 같은데요.  number값을 이상인 값이 mid 위치에서 발견되었다면  왼쪽으로 더 가다보면 아예 작은 수를 만나게 되고 left와 right의 역전 현상이 발생되어 멈춥니다. 멈추기 전에 우리는 가장 마지막에 arr[mid] >= number인 상황을 lower_bnd에 저장한 상황이죠. 

int Binary_Search_Lower_Bound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int lower_bnd = -1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] >= number)
        {
            lower_bnd = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    return lower_bnd;
}

범위를 좁혀가는 상황을 그림으로 표현했습니다.

 

- C++의 lower_bound 사용

C++에서는 라이브러리 함수 형태로 lower bound를 지원합니다. 아래와 같은 형식을 사용하게 되는데요. 사용법은 이렇습니다. 


lower_bound( 정렬한 배열 포인터, 정렬한 배열 포인터의 끝 주소, 값) - 정렬한 배열 포인터

여기서 정렬한 배열의 포인터는 알겠는데, 정렬한 배열 포인터의 끝 주소값은 어떻게 구할까요? 그냥 마지막 원소의 주소를 넣어주거나 배열의 주소 + 배열의 사이즈로 넣어주면 됩니다. 

lower_bound의 반환 값은 하한값의 주소를 돌려주기 때문에 만약 index를 얻으려면 정렬한 배열 포인터를 빼주면 됩니다. 이 함수의 사용법은 밑의 예제 코드에서 upper_bound의 함수와 같이 사용해보도록 하겠습니다.

상한이란? (Upper Bound)

특정 값 K보다 큰 값이 처음으로 나오는 위치가 됩니다. 즉, K값 초과인 값이 맨 처음으로 나오는 위치입니다. 몇 가지 예를 들어볼까요?

배열
1 2 2 4 4 5 6 6 6 9 9
upper_bound
upper bound( 4 ) 5
upper bound( 5 ) 6
upper bound( 9 ) -1 

이 역시 Binary Search로 구현되는데요. 구현한 모습은 아래와 같습니다. 중간의 비교문이 반대로 됐음을 알 수 있죠? 이것은 arr[mid]의 값이 number의 이하일때 number와 최대한 같은 값의 index를 찾기 위함입니다.

 

 

int Binary_Search_Upper_Bound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int upper_bnd=-1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] <= number)
        {
            upper_bnd = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    return upper_bnd+1 >= N ? -1: upper_bnd+1;
}

 

만약 이렇게 돼서 while루프가 멈추었다면 arr[upper_bnd]값은 number값 초과 직전의 값일 것입니다. 그렇다면 arr[upper_bnd+1]의 값은 number보다 큰 값일 테지요. 그래서 마지막 return에서 +1을 해주는데, 이것이 배열의 사이즈를 넘어갈 수 있으니까 사이즈 체크하여 return합니다. 

C++에서 당연히 lower_bound함수가 존재하듯 upper_bound의 함수 역시 존재하며 사용법은 동일합니다. 단, 아래와 같이 사용할때 상한 값을 못찾아줄때도 있는데, 이때는 배열의 인덱스를 넘어가는 값을 갖게됩니다.


  upper_bound(정렬한 배열 포인터, 정렬한 배열 포인터의 끝 주소, 값) - 정렬한 배열 포인터

 

이제까지 설명한 내용을 예제 코드를 통해서 확인해보세요. 직접 구현한 BinarySearch 형식의 upper_bound, lower_bound도 같이 구현되어있습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100];
int N = 11;
int BinarySearchLowerBound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int lower_bnd = -1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] >= number)
        {
            lower_bnd = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    return lower_bnd;
}

int BinarySearchUpperBound(int s, int e, int number)
{
    int left=s,right=e,mid;
    int upper_bnd=-1;
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (arr[mid] <= number)
        {
            upper_bnd = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    return upper_bnd+1 >= N ? -1: upper_bnd+1;
}


int main(void) {


    arr[0] = 4; arr[1] = 2; arr[2] = 4; arr[3] = 1; arr[4] = 9;
    arr[5] = 2; arr[6] = 6; arr[7] = 6; arr[8] = 6; arr[9] = 9, arr[10] = 5;
    
    //정렬
    sort(arr, arr + N);

    printf("정렬된 배열\n");
    for (int i = 0; i < N; i++) printf("%d ",arr[i]);
    printf("\n");
    
    printf("Lower Bound\n");

    printf("%d lower bound:%d\n", 4, BinarySearchLowerBound(0, N - 1, 4));
    printf("%d lower bound:%d\n", 5, BinarySearchLowerBound(0, N - 1, 5));
    printf("%d lower bound:%d\n", 2, BinarySearchLowerBound(0, N - 1, 2));
    printf("%d lower bound:%d\n", 1, BinarySearchLowerBound(0, N - 1, 1));
    printf("%d lower bound:%d\n", 9, BinarySearchLowerBound(0, N - 1, 9));

    printf("%d lower bound:%d\n", 4, lower_bound(arr, arr + N, 4) - arr);
    printf("%d lower bound:%d\n", 5, lower_bound(arr, arr + N, 5) - arr);
    printf("%d lower bound:%d\n", 2, lower_bound(arr, arr + N, 2) - arr);
    printf("%d lower bound:%d\n", 1, lower_bound(arr, arr + N, 1) - arr);
    printf("%d lower bound:%d\n", 9, lower_bound(arr, arr + N, 9) - arr);
  

    printf("Upper Bound\n");

    printf("%d upper bound:%d\n", 4, BinarySearchUpperBound(0, N - 1, 4));
    printf("%d upper bound:%d\n", 5, BinarySearchUpperBound(0, N - 1, 5));
    printf("%d upper bound:%d\n", 2, BinarySearchUpperBound(0, N - 1, 2));
    printf("%d upper bound:%d\n", 1, BinarySearchUpperBound(0, N - 1, 1));
    printf("%d upper bound:%d\n", 9, BinarySearchUpperBound(0, N - 1, 9));

    printf("%d upper bound:%d\n", 4, upper_bound(arr, arr + N, 4) - arr);
    printf("%d upper bound:%d\n", 5, upper_bound(arr, arr + N, 5) - arr);
    printf("%d upper bound:%d\n", 2, upper_bound(arr, arr + N, 2) - arr);
    printf("%d upper bound:%d\n", 1, upper_bound(arr, arr + N, 1) - arr);
    printf("%d upper bound:%d\n", 9, upper_bound(arr, arr + N, 9) - arr);   //배열의 인덱스 초과된 값이 나옴
  
}

 

 

그리고 위 코드의 결과입니다. 마지막 upper_bound의 값이 다름을 확인해보세요.

 

 

전체 코드의 결과

 

반응형
블로그 이미지

REAKWON

와나진짜

,

이진탐색


배열에서 어떤 원소를 찾을때 그 원소가 있는지 어떻게 찾을 수 있을까요?b가장 간단한 방법은 아무래도 for루프를 실행하면서 하나하씩 일치하는지 검색하는 방법이겠죠?


너무 쉽습니다.

int arr[10] = { 3,5,6,8,9,11,14,15,18,20 };
int i;
int data = 18;
int found = -1;
for (i = 0; i < sizeof(arr); i++)
	if (arr[i] == data) found = arr[i];

printf("found:%d\n", found);
이러한 탐색시간은 O(n)에 해당합니다. 배열원소를 하나하나씩 전부 일치하는지 확인하기 때문이죠.

이보다 빠르게 찾을 수는 없을까요? 이 탐색시간을 O(logn)으로 수행할 수 있는 방법이 바로 이진탐색(Binary Search)입니다.


개념

이진탐색은 우선 정렬된 배열에서만 사용가능합니다. 정렬되지 않았다면 정렬을 해주어야하지요. 

또한 이진탐색은 3개의 변수가 사용이 됩니다. 바로 left, mid, right이지요. 초기상태에서 배열의 가장 첫번째를 가리키고 있는 left, 배열의 가장 끝을 가리키고 있는 right, left와 right의 중간을 가리키고 있는 변수가 mid입니다.


우리가 찾는 원소를 data라고 합시다. 우리는 mid의 값을 중요하게 생각해야 돼요. mid자리에 있는 원소가 data와 같다면 그 원소를 찾게 된 것이죠.


만약 mid자리에 있는 원소보다 data가 크다면 left~mid까지 범위는 탐색할 필요가 없게 되지요. 반대로 mid자리 원소보다 data가 작다면 mid~right까지의 범위는 탐색할 필요가 없습니다.


찾지 못 한다면 범위를 바꾸어줘야합니다. left~mid까지의 범위를 탐색할 필요가 없다면 이제 left=mid+1이 되고 mid 역시 left, right의 중간값인 (left+right)/2가 됩니다. 그 반대도 역시 마찬가지죠. 정리하자면 이렇습니다.





1. 찾을 data가 배열의 mid보다 크다면 mid+1부터 right까지 검색

2. 찾을 data가 배열의 mid보다 작다면 left부터 mid-1까지 검색

이제 실제로 어떻게 데이터가 검색되는지 보도록하지요.


배열의 원소 arr = { 3, 5, 6, 8, 9, 11, 14, 15, 18, 20}이라고 칩시다.

다음은 여기서 18을 찾는 과정을 보여줍니다.



우선 초기에 left=0, mid=4, right=9입니다. mid의 값은 (left+right)/2로 계산된 값입니다. arr[mid]와 data를 비교해보니 data가 더 크군요. 그러니까 left와 mid까지의 범위는 볼 필요가 없습니다. 정렬된 배열이기 때문에 18보다 작은 것들은 left~mid까지이니까요.




이제 범위를 옮기도록 하지요. left=mid+1이 되고 mid는 그 중간 값인 (left+right)/2가 됩니다. 이제 다시 arr[mid]와 data를 비교해보니 data가 더 크지요? 다시 범위를 바꿉니다



이제 left와 mid는 같은 값이 되고 다시 arr[mid]와 data를 비교해보니 일치합니다. data가 배열에 있다는 것을 알게 됐습니다.


만일 data를 찾지 못한다면 left와 right는 서로 뒤집히게 됩니다. 그러니까 left가 right보다 더 크게 변한다는 의미입니다.



구현


아래코드는 원소가 존재한다면 몇번째에 위치하는지 인덱스를 구해냅니다. 구현을 통해서 위의 결과를 확인해보세요. 

int binarySearch(int *arr,int size,int data) {
	int left = 0;
	int right = size - 1;
	
	while (left<=right) {
		int mid = (left + right) / 2;
		if (arr[mid] == data)
			return mid;
		if (arr[mid] > data)
			right = mid - 1;
		else
			left = mid + 1;
	}

	return -1;
}


초기 left=0, right=size-1입니다. 가장 처음과 끝을 가리키고 있지요. while루프의 탈출조건은 left가 right보다 같거나 작을때까지 입니다. 


while루프에서는 우선 mid의 값을 구하고 이 mid 원소와 data를 비교하여 같은지 확인합니다. 원소를 찾지 못하면 left와 right의 값을 바꿉니다.

간단하죠?


이진탐색은 재귀함수로도 간단하게 구현이 가능합니다.


int binarySearch(int *arr,int left,int right,int data) {
	if (left > right) return -1;

	int mid = (left + right) / 2;
	
	if (arr[mid] == data) return mid;
	if (arr[mid] > data)
		return binarySearch(arr, left, mid - 1, data);
	return binarySearch(arr, mid + 1, right, data);
}


재귀함수도 너무 간단하죠? 기자사례는 위의 while루프와 같다는 것을 알 수 있습니다. 재귀함수의 종료 조건이되지요.


그 후 내부 코드는 while루프의 내부 코드와 유사하다는 것을 알 수 있습니다. 그렇죠?


아참, 주의할것은 호출할때 binarySearch(arr,0, (sizeof(arr)/sizeof(int))-1, data)로 호출해야합니다. 만약 arr의 크기가 10이라면 9를 right의 매개변수로 전달하는 것이죠. 왜냐면 크기가 10인 배열의 마지막 인덱스는 9이기 때문이죠.


시간복잡도

결국 이진탐색은 반으로 계속 줄여가면서 원소를 탐색하기 때문에 시간복잡도는 O(logn)이라는 사실을 알 수 있습니다. O(n)에 비해서는 훨씬 빠른 속도입니다.




하지만 배열이 정렬된 상태여야 된다는 점이 조금 아쉬운 부분이기는 하지만 하나의 배열에서 검색을 자주하는 상황이라면 한번 정렬만 하면 다음부터는 계속 O(logn)의 속도로 원소를 찾을 수 있죠.


반응형
블로그 이미지

REAKWON

와나진짜

,