[개념] 이진탐색

순차 탐색

최악의 시간 복잡도: O(N)

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

보통 정렬되지 않은 리스트에서 데이터를 찾을 때 사용

#include <stdio.h>
#include <string>
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int num;
    vector<string> str;
    string target;
    int ans;
    cin >> num >> target;

    for (int i = 0; i < num; i++) {
        string strTmp;
        cin >> strTmp;
        str.push_back(strTmp);
    }
    for (ans = 0; ans < num; ans++) {
        if (str[ans] == target) {
            break;
        }
    }
    cout << ans+1;
}

---

이진탐색 : 반으로 쪼개면서 탐색하기

시간복잡도: O(logN)

배열 내부가 정렬되어있어야만 사용가능

#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;

int cnt;
vector<int> num;
int target;

int func(int left, int right) {
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (num[mid] == target) {
        return mid;
    }
    else if (num[mid] > target) {
        return func(left, mid - 1);
    }
    else {
        return func(mid + 1, right);
    }

}

int main (){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> cnt >> target;
    for (int i = 0; i < cnt; i++) {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    sort(num.begin(), num.end());
    int ans = func(0, cnt-1);
    if (ans == -1) {
        cout << "원소가 존재하지 않습니다.";
        return 0;
    }
    cout << ans+1;

}

---

Parametric Search (파라메트릭 서치)

최적화 문제를 결정하는 문제로 바꿔서 해결하는 기법

⇒ 결정하는 문제 = '예' '아니오'로 대답

ex ) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으려는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁힐 수 있다

떡볶이 떡 자르기 문제

• '떡볶이 떡 자르기' 문제를 예로 하면 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복적으로 조정한다
• 현재 이 높이로 자르면 조건을 만족할 수 있는가 → 예 vs 아니오
• 범위로 좁힐 때는 이진 탐색 원리를 이용해 절반찍 좁혀나간다

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt;
    int etc;
    vector<int> rice;
    cin >> cnt >> etc;
    for (int i = 0; i < cnt; i++) {
        int tmp;
        cin >> tmp;
        rice.push_back(tmp);
    }
    int left, right;
    sort(rice.begin(), rice.end());
    left = 0;
    right = rice.back();
    int ans, mid;

    while (left < right) {
        ans = 0;
        mid = (left + right) / 2;
        for (int i = 0; i < cnt; i++) {
            int tmp = rice[i] - mid < 0 ? 0 : rice[i] - mid;
            ans += tmp;
        }
        if (ans == etc)  break;
        else if (ans < etc) {
            right = mid - 1;
        }
        else {
            // 적어도 M만큼의 떡을 얻기 위해
            result = mid;
            left = mid + 1;
        }
    }
    cout << result;

}