[알고리즘] 이분 탐색

이분탐색이란

---

1. 배열 크기를 절반으로 줄이면서 답을 찾는것

   • aka. up/down 놀이

2. 반복문으로 구현

3. O(logn)

4. 입력 범위 N이 큰편

5. 미리 정렬 필수
   
   

이분탐색 방법

---

• 이분탐색 대상인 원소를 트리에 넣기 (=BST)
• 중위 순회를 하면 배열이 나오게됨.
  - LEFT 서브트리 → ROOT 노드 → RIGHT 서브트리
• STL 함수가 존재하긴 하지만, 원소 존재 여부만 리턴하므로, 직접 구현하는 방법을 알아야함
  
  

Parametric 탐색이란

---

• 최적화 문제를 결정문제로 바꾸어 풀기 (YES/NO로)

• ex1) 자동차를 탈 수 있는 가장 어린 사람의 번호는? (19세 이상만 가능)
  → 자동차를 탈 수 있는 사람인지 결정하는 문제로 바꾸어 생각하기

• 나이순으로 정렬이 되어있는 상태에서, 이분탐색을 하는것.

• 다만 정확한 숫자를 찾는 것은 아니므로, 자동차를 탈 수 있는 대상을 찾았다 하더라도, 왼쪽에 있는 사람도 탈 수 있는 나이인지 확인해야함.

• ex2) 공유기 C개를 설치할때, 가장 인접한 공유기 사이의 최대 거리는?
  → 가장 인접한 공유기 사이 거리가 K일때, C개를 설치할 수 있는가?
  → YES인 애들중에서 최댓값이 최대거리인것
  → 인덱스를 거리로 두고, 원소값이 바로 최대 공유기 개수

• 시간복잡도 = O(logn)
  
  

정리

---

• 배열 원소가 정리되어있고, 이분탐색으로 풀 수 있다면, 이분탐색이 가장 빠른 방법
• 코테에서는 이분탐색이 대놓고 나오진 않고, Parametric 탐색으로 많이 나옴
• 최대, 최소 Keyword 주의하기
• 효율성 테스트로 출제 많음
  
  

문제풀이 [BOJ 1920]

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> arr;

int binary_search(int left, int right, int target) {
    //재귀로 하면 너무 오래걸림 절대 안됨
    while(left <= right) {
        int mid = (left + right) / 2;
        if(arr[mid] == target) return 1;
        else if (arr[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    return 0;
}

int main() {
    int n, m, input;
    cin >> n;
    arr.assign(n, 0); //선언 후에 이렇게 초기화할 수 있구나
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    sort(arr.begin(), arr.end());
    
    cin >> m;
    for(int i = 0; i < m; i++) {
        cin >> input;
        cout << binary_search(0, n-1, input) << "\n";
    }
}