upper_bound

• 이진 탐색을 이용하는 것으로 $nlog(n)$의 시간복잡도를 가진다.
• 이진 탐색을 이용하기 때문에 입력되는 배열은 오름차순 정렬이 되어있어야 한다.
• 반환 값은 iterator이므로 인덱스를 알기 위해서는 배열 첫번째 주소를 빼주어야한다.
• 찾는 값을 초과하는 첫번째 인덱스를 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	
	vector<int> arr = { 1, 3, 4, 7, 9 };

	cout << upper_bound(arr.begin(), arr.end(), -1) - arr.begin() << '\n'; // 0
    cout << upper_bound(arr.begin(), arr.end(), 3) - arr.begin() << '\n'; // 2
    cout << upper_bound(arr.begin(), arr.end(), 5) - arr.begin() << '\n'; // 3

	return 0;
}

• -1을 초과하는 첫번째 수는 배열의 첫번째에 있기 때문에 인덱스 번호 0이 출력된다.
• 3을 초과하는 첫번째 수는 4이기 때문에 인덱스 번호 2가 출력된다.
• 5를 초과하는 첫번째 수는 7이기 때문에 인덱스 번호 3이 출력된다.

⭐ 그렇다면 찾는 값을 초과하는 수가 배열에 없다는 어떤 값을 출력할까?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	
	vector<int> arr = { 1, 3, 4, 7, 9 };

	cout << upper_bound(arr.begin(), arr.end(), 9) - arr.begin() << '\n'; // 5
	cout << upper_bound(arr.begin(), arr.end(), 10) - arr.begin() << '\n'; // 5

	return 0;
}

• 9를 초과하는 값이 배열에 없기 때문에 배열의 끝을 가리키는 5가 출력된다. 이는 배열의 마지막 인덱스+1 과 같은 값이다.
• 10을 초과하는 값이 배열에 없기 때문에 5가 출력된다.

lower_bound

• 이진 탐색을 이용하는 것으로 $nlog(n)$의 시간복잡도를 가진다.
• 이진 탐색을 이용하기 때문에 입력되는 배열은 오름차순 정렬이 되어있어야 한다.
• 반환 값은 iterator이므로 인덱스를 알기 위해서는 배열 첫번째 주소를 빼주어야한다.
• 찾는 값 이상 값을 가지는 첫번째 인덱스를 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	
	vector<int> arr = { 1, 3, 4, 7, 9 };

	cout << lower_bound(arr.begin(), arr.end(), -1) - arr.begin() << '\n'; // 0
	cout << lower_bound(arr.begin(), arr.end(), 1) - arr.begin() << '\n'; // 0
	cout << lower_bound(arr.begin(), arr.end(), 2) - arr.begin() << '\n'; // 1

	return 0;
}

• 0 이상의 값인 1이 첫번째 인덱스에 있기 때문에 0이 출력된다.
• 1 이상의 값인 1이 첫번째 인덱스에 있기 때문에 0이 출력된다.
• 2 이상의 값인 3이 두번째 인덱스에 있기 때문에 1이 출력된다.

⭐ 그렇다면 찾는 값 이상의 값이 배열에 있지 않으면 어떤 값이 출력될까?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	
	vector<int> arr = { 1, 3, 4, 7, 9 };

	cout << lower_bound(arr.begin(), arr.end(), 10) - arr.begin() << '\n'; // 5

	return 0;
}

• 10 이상의 값은 배열에 없기 때문에 upper_bound와 마찬가지로 배열의 끝을 가리키는 배열의 마지막 인덱스+1과 같은 5가 출력된다.