[C++] binary_search, lower_bound, upper_bound

C++

int BinarySearch(vector<int> arr, int key) {
	int M = 0;
	int L = 0;
	int R = arr.size();
	while (L < R) {
		M = (L + R) / 2;
		if (arr[M] == key)return M;
		if (arr[M] > key) 
			R = M;
		else 
			L = M + 1;
	}
	return -1;
}

정렬상태인 데이터가 입력으로 들어왔을 때 키값과 일치하는 인덱스를 반환한다. 일치하는 데이터가 없으면 -1을 반환한다.

이진탐색은 데이터의 존재 여부만을 검사한다. STL의 binary_search의 반환형이 bool임에 그 이유를 짐작할 수 있다. 가끔 다른 구현체에 값이 같은지 검사하지 않고 리턴문에서 검사하는 코드가 있는데 해당 코드는 lower_bound 또는 upper_bound 일 것이다.

int LowerBound(vector<int> arr, int key) {
	int M = 0;
	int L = 0;
	int R = arr.size();
	while (L < R) {
		M = (L + R) / 2;
		if (arr[M] >= key) {    //조건문이 UpperBound와 다르다.
			R = M;
		} else {
			L = M + 1;
		}
	}
	return L;
}

LowerBound는 key 이상인 값이 처음 나오는 위치를 반환한다. 따라서 조건문에서 >=가 사용된다.

int UpperBound(vector<int> arr, int key) {
	int M = 0;
	int L = 0;
	int R = arr.size();
	while (L < R) {
		M = (L + R) / 2;
		if (arr[M] > key) {
			R = M;
		} else {
			L = M + 1;
		}
	}
	return L;
}

UpperBound는 key 초과인 값이 처음 나오는 위치를 반환한다. 따라서 조건문에서 > 가 사용된다.