binary search & lower bound & upper bound [c++ 구현]

 

' binary search & lower bound & upper bound '

 

코딩 테스트를 하다보면 이분 탐색을 자주하게 된다. 대부분 내장함수로 사용하면 되지만,  문제 종류에 따라서 직접 구현해 조건을 더해야 풀 수 있는 경우가 있다. 

c++ 기준으로 이진 탐색 함수는 총 3가지가 있다. 이 세가지 모두 이진 탐색이 기반인 알고리즘이므로 데이터가 오름차순으로 정렬이 되어 있어야 한다. 

1. [ #include<algorithm> ]  std::binary_search

• val값이 있는지 없는지 확인하는 알고리즘 [ return bool ] 
• std::lower_bound를 이용하여 구현한 알고리즘.

 

2. [ #include<algorithm> ] std::lower_bound

• val값의 시작 위치를 찾는 알고리즘

 

3. [ #include<algorithm> ] std::upper_bound

• val값보다 처음으로 큰 값, 즉 val이 값이 끝나고 그 다음 값의 위치를 찾는 알고리즘 

 

_EXPORT_STD template <class _FwdIt, class _Ty>
_NODISCARD _CONSTEXPR20 bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // test if _Val equivalent to some element
    return _STD binary_search(_First, _Last, _Val, less<>{});
}


_EXPORT_STD template <class _FwdIt, class _Ty>
_NODISCARD _CONSTEXPR20 _FwdIt upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // find first element that _Val is before
    return _STD upper_bound(_First, _Last, _Val, less<>{});
}


_EXPORT_STD template <class _FwdIt, class _Ty>
_NODISCARD _CONSTEXPR20 _FwdIt lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // find first element not before _Val
    return _STD lower_bound(_First, _Last, _Val, less<>{});
}

모두 탐색하려는 대상이나 목적이 다르기 때문에 ex) val = 4를 넣었을 때 3가지 함수의 결과 값은 아래와 같이 다르다. 

 

구현 코드 

 

1. binary_search 

int binary_search_Func(int pStart, int pEnd, int pTarget)
{
	if (pStart > pEnd)
	{
		return 0; 
	}
	int mMid = (pStart + pEnd) / 2; 
	
	if (arr[mMid] == pTarget)
	{
		return mMid; 
	}
	else if (arr[mMid] > pTarget)
	{
		binary_search_Func(pStart, mMid - 1, pTarget);
	}
	else if (arr[mMid] < pTarget)
	{
		binary_search_Func(mMid + 1, pEnd, pTarget);
	}
}

 

2. lower_bound

int Lower_Bound_Func(int pStart, int pEnd, int pTarget)
{
	if (pStart >= pEnd)
	{
		return pStart;
	}
	int mMid = (pStart + pEnd) / 2;

	if (arr[mMid] >= pTarget) 
	{
		Lower_Bound_Func(pStart, mMid, pTarget);
	}
	else if (arr[mMid] < pTarget)
	{
		Lower_Bound_Func(mMid + 1, pEnd, pTarget);
	}
}

 

3. upper_bound

int Upper_Bound_Func(int pStart, int pEnd, int pTarget)
{
	if (pStart >= pEnd)
	{
		return pStart;
	}
	int mMid = (pStart + pEnd) / 2;

	if (arr[mMid] > pTarget)
	{
		Upper_Bound_Func(pStart, mMid, pTarget);
	}
	else if (arr[mMid] <= pTarget)
	{
		Upper_Bound_Func(mMid + 1, pEnd, pTarget);
	}
}

 

※ 참고

lower_boud와 upper_bound를 다 하나씩 하나씩하면서 생각하지말고 마지막 경우만 생각하면 코드를 쉽게 짤수 있다. 

파라미터의 val 값이 = 4 일 때,

lower_bound와 upper_bound의 동일한 점을 먼저 생각하자. 

첫번째.  종료 조건 : if (pStart >= pEnd)

두번째.  mid의 값 : (start + end) / 2 

 

다른 점은? 

lower_bound에서 원하는 값은 val값의 시작 위치  (4), upper_bound에서는 val값보다 처음으로 큰 값 (5) 이다. 

 

그러므로, 종료 조건을 떠올리며  if (pStart >= pEnd) lower_bound는 end를 움직이고 upper_bound는 start를 움직이도록해줘야 한다.  

<< lower_bound >> mid의 값은 4, val은 4 같거나 클 때 end는 = mid  작을 때 start = mid + 1

<< upper_bound >> mid의 값은 4, val은 4 같거나 작을 때 start = mid + 1 클 때는 end = mid