이분탐색(1)

 

https://www.youtube.com/watch?v=3TkaOKHxHnI&t=33s

---

이진 탐색 코드

int a[100000];
int n;

int binarysearch(int target){
    int st=0; int en=n-1;
    while(st<=en){
        int mid=(st+en)/2;
        if(a[mid]>target) en=mid-1;
        if(a[mid]<target) st=mid+1;
        if(a[mid]==target) return 1;
    }
    return 0; //st>en인 경우 탈출한다
}

---

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

10816번: 숫자 카드 2

upper_bound는 주어진 값을 초과하는 첫 번째 요소의 위치를 반환한다.

lower_bound는 주어진 값보다 크거나 같은 첫 번째 요소의 위치를 반환

a[5] = {1,1,2,3} 일때 upper_bound로 1을 찾으면 인덱스 2를 반환하고, lower_bound로 1을 찾으면 인덱스 0을 반환한다.

또한 이 배열에서 0을 찾으려고 할 경우 0은 배열에 존재하지 않으므로 upper bound는 0을 초과하는 첫 번째 요소의 위치인 0번 인덱스를, lower bound는 0과 같거나 큰 첫 번째 요소의 위치를 반환하므로 0을 반환한다.

#include <bits/stdc++.h>
using namespace std;
int a[500005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    int m; cin>>m;
    while(m--){
        int t; cin>>t;
        cout<<upper_bound(a,a+n,t)-lower_bound(a,a+n,t)<<' ';
    }
    return 0;
}

---

이분 탐색 주의사항

1. 배열은 정렬되어 있어야 한다.

2. 무한 루프에 빠지면 안된다.

- mid가 배열을 절반으로 쪼개지 못하는 경우 무한 루프에 빠짐

---

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

2295번: 세 수의 합

혼자 하다가 two를 정렬하는 것을 잊고 몇 번 틀렸다...

바로 cout을 하지 말고 ans를 갱신하는 것도 시간초과가 나지 않는다.

#include <bits/stdc++.h>
using namespace std;
int a[1003];
vector<int> two;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n;i++)
        for(int j=i;j<n;j++)
            two.push_back(a[i]+a[j]);
    sort(two.begin(),two.end());
    //two + z = k
    //two = k-z 옳다면 k를 출력
    for(int k=n-1;k>=0;k--){
        for(int z=0;z<n;z++){
            if(binary_search(two.begin(),two.end(),a[k]-a[z])){
                cout<<a[k]; return 0;
            }
        }
    }
    return 0;
}

---

Parametric Search

뭔가 Pspice에서 자주 보는 그래프라 반가웠다

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

1654번: 랜선 자르기

1부터 2^31 -1의 범위를 이분탐색으로 돌면서 최적해를 찾는다. 솔직히 쉽지 않다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int k,n,a[10003];

bool solve(ll x){
    ll cur=0;
    for(int i=0;i<k;i++) cur+=(a[i]/x); //vscode에서 괄호치면 문제가 생겼었는데 앞에 (int) 두면 해결됨
    return cur>=n;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>k>>n;
    for(int i=0;i<k;i++) cin>>a[i];
    ll st=1; ll en=0x7fffffff;
    while(st<en){
        ll mid=(st+en+1)/2;
        if(solve(mid)) st=mid;
        else en=mid-1;
    }
    cout<<st;
    return 0;
}

---