자료구조 - Lower bound & Upper bound

• Lower bound & Upper bound : 이분탐색 (Binary Search) 을 활용한 알고리즘으로, 중복된 값의 시작 위치와 끝 위치를 찾는데 유용
• 기본적으로 정렬이 되어있어야 하며, 시간복잡도는 O(logn) 이다.
  
  

Lower bound : 중복된 값들이 있는 배열에서 같은 값이 처음 나오는 위치

Upper bound : 중복된 값들이 있는 배열에서 같은 값이 연속적으로 나오다가 연속이 끊기는 위치

• 예시

배열 array[] = {1, 2, 2, 5, 8, 8, 8, 11, 11}
1의 Lower bound : 0
1의 upper bound : 1
-> 배열에서 1의 개수 : 1 - 0 = 1


8의 lower bound : 4
8의 upper bound : 7
-> 배열에서 8의 개수 : 7 - 4 = 3

• Lower bound 구현 코드

int lowerBound(int a[], int left, int right, int num)
{
	int middle;
    while(left < right)
    {
    	middle = (left + right) / 2;
        if(a[middle] >= num)
        {
        	right = middle;
        }
        else
        {
        	left = middle + 1;
        }
   	}
    return left; // left = right 
}

• Upper bound 구현 코드

int upperBound(int a[], int left, int right, int num)
{
	int middle;
    while(left < right)
    {
    	middle = (left + right) / 2;
        if(a[middle] <= num)
        {
        	left = middle + 1;
        }
        else
        {
        	right = middle;
        }
    }
    return left; // left = right
}