이진탐색(이분탐색)(Binary Search)란?
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
- 일반적인 탐색 기법으로는 앞에서부터 요소를 순차적으로 탐색하기 때문에 시간 복잡도는 데이터의 개수만큼 이 된다. 즉 O(n) 이 된다.
- 만일 데이터의 개수가 무수히 많아진다면 굉장히 비효율적인 알고리즘이 된다.
- 하지만 이분 탐색을 사용하면 O(log n) 의 시간 복잡도로 탐색을 수행할 수 있다.
이분탐색 구현코드
void a()
{
int arr[501];
for (int i = 1; i < 501; i++)
arr[i] = i;
int target; // 타겟 값
cin >> target;
int left = 1, right = 500; // left, right 초기화
while (left <= right)
{
//중앙값 초기화
int mid = (left + right) / 2;
if (mid == target)
{
cout << "Search" << '\n';
break;
}
else if (mid > target)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
}이제 이분탐색을 할 때 사용하는 함수를 알아보자!!
1. binary_search()함수
binary_search(arr_begin,arr_end,find_value) :
검색해주는 함수로서 찾는 값이 존재하면 True, 아니면 False를 리턴한다.
이를 코드에 적용시켜보면
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n, m;
vector<string>vec;
vector<string>vec2;
string name;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> name;
vec.push_back(name);
}
sort(vec.begin(), vec.end());
string str;
for (int j = 0; j < m; j++)
{
cin >> str;
if (binary_search(vec.begin(), vec.end(), str))// search를 하면
{
vec2.push_back(str);
}
}
sort(vec2.begin(), vec2.end());
cout << vec2.size() << '\n';
for (int i = 0; i < vec2.size(); i++)
{
cout << vec2[i] << '\n';
}
return 0;
}간단하게만 설명하자면
if (binary_search(vec.begin(), vec.end(), str))
{
vec2.push_back(str);
}str이 있다면 vec2라는 백터에 str을 저장한다는 코드이다.
다음으론 upper_bound()와 lower_bound()를 알아보자.
upper_bound, lower_bound 는 오름차순 정렬이 되있다는 전제가 깔려있어야 한다!
2. lower_bound 란?
- 이진탐색(Binary Search)기반의 탐색 방법이다.
- lower_bound는 찾으려 하는 key 값이 "없으면" key 값보다 큰(바로 다음 index) 정수를 찾는다.
- 같은 원소가 여러개 있으면 가장 앞에 있는 index 값을 구한다.
3. upper_bound 란?
- lower_bound와 마찬가지로 이진 탐색(Binary Search) 기반의 탐색법이다.
- upper_bound는 key 값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 이다!
- 같은 원소가 여러 개 있으면 가장 앞에 있는 index값을 구한다.
lower_bound : 찾고자 하는 값 이상이 처음 나타나는 위치
upper_bound : 찾고자 하는 값의 다음 값이 최초로 나타나는 위치
즉, 1 2 4 4 6 7에서
lower_bound(~,~,4)의 결과 : 2 (4 이상의 값이 처음 나타나는 위치)
upper_bound(~,~,4)의 결과 : 4 (4를 초과하는 값이 처음 나타나는 위치)
(추가)만약 주어진 수 보다 큰 수를 입력하게 되면 저 위에 예를 들면 8이 입력됐다? 그럼 index + 1 이 출력 즉 6이 출력된다!
이것을이용해서 upper - lower 을 빼주면 2가 나오고
이 값은 저장된 4의 개수가 된다.
for (int i = 0; i < m; i++)
{
cin >> num;
auto a = lower_bound(vec.begin(), vec.end(), num) - vec.begin();
auto b = upper_bound(vec.begin(), vec.end(), num)- vec.begin();
cout << b - a << " ";
}ex) 중복값을 구하는 문제라면
1 1 2 3 4 4 5 6 6 7이 vector에 입력이 되어있고 num에 6이 들어간다고 한다면
a에는 6이 처음 발견되는 index인 7
b에는 6보다 큰 값이 처음 발견되는 index 값인 9가 들어가게 되고
b - a를 해준다면 num값이 vector안에 몇 개가 들어가 있는지 쉽게 알 수 있다.
정렬을 공부하면서 아직도 우물 안 개구리고 부족한 부분이 많다고 느낀다..
포기하지 않고 계속 나아간다면 나도 어느샌가 알고리즘 고수가 되어있을 것이라고 생각한다.
BFS, DFS 등등 열심히 차근차근 공부해 보자!
끗!
