|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int arr[10] = { 1,2,2,3,4,5,6,6,7,9 };
void go_lower(int a, int low, int high)
{
int mid;
while (low < high)
{
mid = (low + high) / 2;
if (arr[mid] < a)
low = mid+1;
else
high = mid;
}
cout << high << '\n';
}
void go_upper(int a, int low, int high)
{
int mid;
while (low < high)
{
mid = (low + high) / 2;
if (arr[mid] <= a)
low = mid + 1;
else
high = mid;
}
cout << high '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int a;
cout << "bound? : ";
cin >> a;
go_lower(a,0,10);
go_upper(a,0,10);
}
|
cs |
주의점 :
1. 반환할때에는 arr의 값을 반환하는게 아닌 위치를 반환해야 한다.
특히 upper_bound 생각할떄 맨 끝이 기준이여도 무언가를 반환해야 하지 않겠는가?
2. mid 값을 low로 옮길때는 low = mid+1 이다. 이유를 알아보자.
ex1) 1 2 2 3 5 lower_bound(2) 를 구해보자. 직관적으로 보면 답은 1이 나올것이다.
low 0 high 4
low 0 high 2
low 0 high 1
여기서 low 가 0번째, high가 1번째 가르키고 있는 상황으로 생각해보자. -> mid는 0번째
arr[mid] < a -> low가 올라와야 한다.
arr[mid] = a -> high가 내려가야 한다.
arr[mid] > a -> high가 내려가야 한다.
근데 low가 mid의 도움으로 0번째에서 1번째로 올라가려면 mid+1을 해줘야 한다.
ex1) 1 2 2 3 5 upper_bound(2) 를 구해보자. 직관적으로 보면 답은 3이 나올것이다.
low 0 high 4 -> mid 2에서
arr[mid] < a -> low가 올라와야 한다.
arr[mid] = a -> low가 올라와야 한다.
arr[mid] > a -> high가 내려가야 한다.
그러면 그 다음은
low 3 high 4
low 3 high 3 (break)