이진 탐색

- 이진 탐색 : 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘. 타 탐색 알고리즘와의 차이점으로는

1. 꼭 정렬된 상태에서 구현되어야 한다.
2. 시간 복잡도가 O(log n)이다.
3. 중앙값 비교를 통한 대상 축소 방식이다.

정도가 되겠다. 데이터의 양이 너무 많을 때(타 탐색 알고리즘을 이용하면 시간 초과가 날 때) 이용하면 좋겠다. 

 

- 이진 탐색의 핵심 이론(오름차순으로 정렬된 데이터에서만 적용)

1. 현재 데이터의 중앙값(mid)을 선택한다.
2. 중앙값 > 타깃 데이터일 때 중앙값을 기준으로 왼쪽을 선택한다. (끝점을 중앙값 바로 이전 데이터로 선택한다.)
3. 중앙값 < 타깃 데이터일 때 중앙값을 기준으로 오른쪽을 선택한다. (시작점을 중앙값 바로 이후 데이터로 선택한다.)
4. 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. 

문제 하나를 풀면서 적용해보자.

https://www.acmicpc.net/problem/1920

#include <bits/stdc++.h> // 1920 수 찾기
using namespace std;
using ll = long long;
ll arr_n[100001];
ll arr_m[100001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr_n[i];
    cin >> m;
    for(int i = 0; i < m; i++)
        cin >> arr_m[i];
    
    for(int i = 0; i < m; i++){
        int check = 0;
        for(int j = 0; j < n; j++){
            if(arr_n[j] == arr_m[i]) check = 1;
        }
        cout << check << '\n';
    }
}

처음 이 문제를 접근한다면 보통 이런식으로 하나의 원소와 다른 배열의 모든 원소와 비교하게 짠다. 하지만 최악의 경우에는 10만 * 10만 = 100억번의 시행이 이루어지게 된다. 이는 시간 초과로 이어진다ㅏ. 이럴 때 이분 탐색을 이용하면 더욱 적 은 시행으로 답을 낼 수 있어 시간 초과가 안나게 된다.

#include <bits/stdc++.h> // 1920 수 찾기
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n;
    vector<int> v(n);
    
    for(int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    
    cin >> m;
    
    for(int i = 0; i < m; i++){
        int target;
        cin >> target;
        
        int start = 0;
        int end = n-1;
        int mid;
        int check = 0; // 존재여부 체크
        
        while(start <= end){
            mid = (start + end) / 2;
            if(v[mid] > target) end = mid - 1;
            else if(v[mid] < target) start = mid + 1;
            else {
                check = 1;
                break;
            }
        }
        cout << check << '\n';
    }
}

이분탐색을 이용하면 탐색 부분의 시간복잡도가 log(100억) 약 32~33이니 확실히 줄어든다. 많은 양의 케이스가 주어지는 경우의 탐색은 이분 탐색을 적극적으로 이용해보자.