[초간결 C++] 이분 탐색 구현(함수 또는 반복문을 이용한 방법)

선형 탐색

• 데이터 전체를 순서대로 순회하면서 탐색한다.
• 시간복잡도 O(N)

이분 탐색

• 😯 정렬된 data에 대해서만 사용 가능하다.
• 시간복잡도 O(logN)
• 매번 탐색 범위가 1/2배가 된다.
• 탐색을 여러 번 해야 할 때 효율적이다.(😯정렬을 할 가치가 있으므로)

이분 탐색 구현(C++)

1. 함수를 이용한 경우

#include <iostream>
#include <vector>
using namespace std;

vector<int> v = {1,3,5,7,11,18,21,33,43,45};

int search(int tar, int l, int r) {
    if(l>r) return -1;

    int mid = (l+r)/2;
    if(v[mid]==tar) return mid;
    if(v[mid]<tar) return search(tar, mid+1, r);
    if(v[mid]>tar) return search(tar, l, mid-1);    
}

int main() {
    int target, len=10;
    
    cin >> target;
    cout << search(target, 1, len-1);
}

2. 반복문을 이용한 경우

#include <iostream>
#include <vector>
using namespace std;

vector<int> v = {1,3,5,7,11,18,21,33,43,45};

int main() {
    int target, len=10;
    int l=1, r=len-1;
    cin >> target;
    
    while(l<=r) {
        int mid = (l+r)/2;
        if(v[mid]==target) {
            cout << mid;
            return 0;
        }
        if(v[mid]>target) r = mid-1;
        else if(v[mid]<target) l = mid+1;
    }
    cout << -1;
}