[Algorithm] 이분탐색

● 이분탐색 : 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 방법

● 선형탐색은 O(N)에 동작하고 이분탐색은 O(lg N)에 동작합니다.

 

● 구현

# BOJ 1920번:수찾기

# include<iostream>
# include<bits/stdc++.h>
using namespace std;
int arr[100005];
int n;
int binarysearch(int target){
    int st,en,mid;
    st=0;
    en=n-1;
    while(st<=en){
        mid=(st+en)/2;
        if(target==arr[mid]){
            return 1;
        }
        else if(target<arr[mid]){
            en=mid-1;
        }
        else{
            st=mid+1;
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m;
    int target;
    
    cin>>n;
    for (int i=0; i<n; i++) {
        cin >> arr[i];
    }
    sort(arr,arr+n);

    cin>>m;
    while(m--){
        cin>>target;
        cout<<binarysearch(target)<<'\n';
    }
    return 0;
}

 

● STL

-  binary_search 이용하기

-  binary_search(배열의 포인터, 배열의 포인터+배열의 크기, 찾고자 하는 값)

- O(lgN)

-  a가 배열이 아닌 vector라면 a.begin(), a.end()를 인자로 넘겨주기

- binary_search STL을 쓸 때 범위는 반드시 오름차순으로 정렬되어 있어야 합니다. 

# BOJ 1920번:수찾기_stl


#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int arr[100005];
int n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m;
    int target;
    
    cin>>n;
    for (int i=0; i<n; i++) {
        cin >> arr[i];
    }
    sort(arr,arr+n); // stl 쓸 때도 정렬 시켜줘야 함

    cin>>m;
    while(m--){
        cin>>target;
        cout<<binary_search(arr,arr+n,target)<<'\n';
    }
    return 0;
}