이분탐색 (Binary Search)

1. 설명

시간 복잡도: O(logn)
merge sort를 공부한 다음에 대충 감을 잡고 있었다.
merge sort가 정렬을 하기 위해 중간값을 기준으로 계속 나눈 것이었다면, 이분탐색은 이미 잘 정렬된 배열을 중간값을 기준으로 크고 작음을 비교하며 배열에서 위치를 찾는다.

2. code

int binarysearch(int target)
{
    int st = 0;
    int ed = n - 1;
    while (st <= ed)
    {
        int mid = (st + ed) / 2;
        if (a[mid] < target)
            st = mid + 1;
        els else if (a[mid] > target)
            ed = mid - 1;
        else
            return (1);
    }
    return (0);
}

찾을 경우 1리턴, 못 찾을 경우 0 리턴

3. lower_bound()

the function returns an iterator pointing to the next smallest number just greater than or equal to that number. If there are multiple values that are equal to val, lower_bound() returns the iterator of the first such value.

4. 문제

문제상 찾고자 하는 수는 무조건 배열안에 있을 것이기 때문에 get()함수의 base condition을 저렇게 만들었다.

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
vector<int> st;

void    get(int num, int st, int ed)
{
    if (v[(st + ed) / 2] == num)
    {
        cout << (st + ed) / 2 << ' ';
        return ; 
    }
    int mid = (st + ed) / 2; 
    if (v[mid] > num)
        get(num, st, mid);
    else
        get(num, mid, ed);
}

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

    int n, num;
    cin >> n;
    while (n--)
    {
        cin >> num;
        st.push_back(num);
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int i = 0; i < st.size(); i++)
        get(st[i], 0, v.size());

    return (0);
}