[탐색] 이분탐색 lower_bound, upper_bound

lower_bound란

이진탐색(Binary Search)기반의 탐색 방법. (배열 또는 리스트가 정렬 되어야 있어야함.)

 : 찾고자 하는 값 이상의 값이 처음 나타나는 "위치" 

	int arr[10] = {1,2,4,5,6,6,7,7,7,9 };
	//lower_bound : 정수 값 찾음
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 10, 6) - arr  << endl; //4
	cout << "lower_bound(7) : " << lower_bound(arr, arr + 10, 7) - arr  << endl; //6
	cout << "lower_bound(8) : " << lower_bound(arr, arr + 10, 8) - arr  << endl; //9
	cout << "lower_bound(9) : " << lower_bound(arr, arr + 10, 9) - arr  << endl; //9

단, 만약 못찾으면 찾고자 하는 값 배열의 마지막 위치를 반환한다.

 

 

upper_bound

lower_bound와 마찬가지로 이진탐색기반의 탐색법 이진탐색(Binary Search)기반이므로 배열이나 리스트가 오름차순으로 정렬 되어야한다.

 : 찾고자 하는 값 초과하는 값이 처음 나타나는 "위치"

	cout << "upper_bound(6) : " << upper_bound(arr, arr + 10, 6) - arr  << endl; //6
	cout << "upper_bound(7) : " << upper_bound(arr, arr + 10, 7) - arr  << endl; //9
	cout << "upper_bound(8) : " << upper_bound(arr, arr + 10, 8) - arr  << endl; //9
	cout << "upper_bound(9) : " << upper_bound(arr, arr + 10, 9) - arr  << endl; //10

단, 만약 못찾으면 찾고자 하는 값 배열의 마지막 위치를 반환한다.