이진탐색을 사용하기 위한 조건 : 정렬되어 있어야 한다.
찾으려는 데이터와 중간점(middle)위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
시간 복잡도 : O(log(N))
1) 재귀를 이용한 구현
#include <iostream>
#include <vector>
using namespace std;
int n, target;
vector<int> v;
int binarySearch(int s, int e, int t) {
if (s > e)
return -1;
int mid = (s + e) / 2;
if (v[mid] == t) {
return mid;
}
else if (v[mid] < t) {
return binarySearch(mid+1, e, t);
}
else {
return binarySearch(s, mid-1, t);
}
}
int main(void) {
cin >> n >> target;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
v.push_back(a);
}
cout << binarySearch(0, n-1, target) + 1 << "\n";
return 0 ;
}2) while문을 이용한 구현
#include <iostream>
#include <vector>
using namespace std;
int n, target;
vector<int> v;
int binarySearch(int t) {
int s = 0;
int e = v.size() - 1;
while (s <= e) {
int mid = (s + e) / 2;
if (v[mid] == t) {
return mid;
}
else if (v[mid] < t) {
s = mid+1;
}
else {
e = mid - 1;
}
}
return - 1;
}
int main(void) {
cin >> n >> target;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
v.push_back(a);
}
cout << binarySearch(target) + 1 << "\n";
return 0 ;
}나의 경우 2번이 편하다.
1번, 2번 아무거나 사용하여도 상관 없다!
파라메트릭 서치(Parametric Search)
- 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제(decision problem)로 바꾸어 해결하는 기법
- 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이분 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.
Lower Bound, Upper Bound
- 이진 탐색으로 돌음
- countByRange 처럼 정렬된 배열에서 a~b까지의 숫자의 개수를 O(logN)으로 찾고자 할때 주로 사용한다.
Lower Bound
- 키값보다 크거나 같은 첫번째 값
- 찾으려고 하는 key 값이 없으면, key 값 초과인 값들 중, 가장 작은 값
Upper Bound
- 키값보다 큰 첫번째 값
- 최댓값보다 더 큰 값을 찾고자 하는 경우에는, 마지막 요소 다음 메모리를 가리키는 iterator(end()와 같은)를 반환한다. 따라서, 이 iterator에 접근하면 쓰레기값을 반환.
직접 구현할 경우는 기존 이진 탐색에서 값을 찾았을 경우 left를 이동할지 right를 이동할지를 생각해 로직을 수정하면된다.
또한 증명하는 방법은 이진탐색은 l~r의 크기가 1 또는 2일 경우를 결국은 지나므로 해당하는 경우를 모두생각해보면 편하다.
1) 직접 구현
#include <iostream>
#include <vector>
using namespace std;
int n, key;
vector<int> v;
// Key 보다 크거나 같은 첫번째 값 반환
int lowerBound() {
int l = 0, r = n-1;
while (l <= r) {
int mid = (l + r) / 2;
if (v[mid] < key) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
return l;
}
// Key보다 큰 첫번째 값
int upperBound() {
int l = 0, r = n-1;
while (l <= r) {
int mid = (l + r) / 2;
if ( v[mid] <= key) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
return l;
}
// 값이 [left, right]인 데이터의 개수를 반환하는 함수
int countByRange() {
int left = lowerBound();
int right = upperBound();
return right - left;
}
int main(void) {
cin >> n >> key;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
v.push_back(x);
}
int cnt = countByRange();
if (cnt == 0) {
cout << -1 << "\n";
}
else {
cout << cnt << "\n";
}
return 0 ;
}2) STL
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, key;
vector<int> v;
// 값이 [left, right]인 데이터의 개수를 반환하는 함수
int countByRange() {
// Key 보다 크거나 같은 첫번째 값 반환
vector<int>::iterator left = lower_bound(v.begin(), v.end(), key);
// Key보다 큰 첫번째 값
vector<int>::iterator right = upper_bound(v.begin(), v.end(), key);
return right - left;
}
int main(void) {
cin >> n >> key;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
v.push_back(t);
}
int cnt = countByRange();
if (cnt == 0) {
cout << -1 << "\n";
}
else {
cout << cnt << "\n";
}
return 0 ;
}'알고리즘 > Template' 카테고리의 다른 글
| [Algorithm][Template] DFS와 BFS (0) | 2022.02.05 |
|---|---|
| [Algorithm][Template] 2차원 배열 동서남북 움직이기 (0) | 2022.01.29 |
| [Algorithm][Template] 순열과 조합 (0) | 2022.01.22 |
| [Algorithm][Template] Prefix Sum, 구간 합 계산 (0) | 2022.01.20 |
| [Algorithm][Template] 투 포인터 (0) | 2022.01.20 |