[c++] 이진탐색에서 size_t 사용할때 유의할점

[해당 글의 내용이 정확하지 않을 수 있습니다. 언제나 피드백 주시면 바로 반영하겠습니다.]

주로 인덱스를 다룰때, 그리고 음수가 들어갈수없는 변수의 경우 size_t 로 설정한다

그래서 for문이나 컨테이너의 크기를 받아올때 size_t를 사용해서 받게된다

그런데 binarySearch를 구현하다가 한가지를 발견하게되었는데,

size_t PmergeMe::binarySearch(int insertNum) {
	int low = 0;
	int mid;
	int high = _main.size() - 1;

	while (low <= high)
	{
		mid = low + (high - low) / 2;
		if (insertNum == _main.at(mid))
			return (mid);
		if (insertNum < _main.at(mid))
			high = mid - 1;
		else
			low = mid + 1;
	}
	if (insertNum > _main.at(mid))
		return (mid + 1);
	else
		return (mid);
}

이 이진 탐색에서 low와 high를 size_t로 변경하게되면, 이진 탐색을 수행하는 도중에 _main.at(mid)에서 예외를 던지게 된다

이유로는 high = mid - 1에서 underflow가 발생해서 size_t 최대값으로 설정되어버리는 것

그렇게 되었을때 while문의 조건이 low <= high 항상 참값을 갖게 되고, 내부에서 해당 벡터 컨테이너에 at으로 접근했을때, 범위를 초과한 곳에 접근하게 되어 std::out_of_range 예외를 발생시킴

 

1. size_t로 설정된 index를 다룰땐, 해당 함수 내부에 size_t로 설정된 값이 음수로 될 여지가 있는지 확인해야함

2. while문의 탈출 조건이 low <= high로 되어있긴한데, 같다는 조건이 붙어서 발생한 것이기도 하다. 하지만 이진탐색 특성상 접근 가능한 인덱스의 범위만 다루어야 하기때문에 해당 조건이 설정된것. 이 조건에 대해서도 한번 생각해야함