[C++] 이분검색(Binary Search) - 기초 문제

이분검색 : 검색 범위를 절반으로 축소해나가면서 찾아가는 검색 방식

기초 문제

#include <stdio.h>
#include <vector>

using namespace std;
int main() {
    int N, M, i;
    
    int lt,rt,mid;
    
    scanf("%d %d",&N, &M);
    vector<int> vec(N);
    
    for(i = 0; i < N; i++){
        scanf("%d", &vec[i]);
        //scanf("%d", tmp);
        //vec.push_back(tmp);
    }
    
    sort(vec.begin(), vec.end());
    
    lt = 0;
    rt = N-1;
    while(lt <= rt){
        mid = (lt+rt)/2;
        if(vec[mid] == M){
            //정답
            printf("%d",mid+1);
            break;
        }
        else if(vec[mid] < M){
            //key는 오른쪽에 있으므로 오른쪽으로 검색 범위 축소
            lt = mid+1;
        }else if(vec[mid] > M){
            //key는 왼쪽에 있으므로 왼쪽으로 검색 범위 축소
            rt = mid-1;
            
        }
    }
    return 0;
}

• 검색하고자 하는 값을 찾을 때까지 배열을 절반으로 잘라나가는 방식이다.
• 즉, 검색이라는 것은 찾고자 하는 것(정답이 될 수 있는 것)을 정해 놓고 맞냐 아니냐를 판단해나가는 것이다.
• 검색하고자 하는 값이 mid index의 값보다 크다면 mid기준으로 오른쪽에 있다는 뜻이므로, lt가 mid+1로 바뀐다
• 검색하고자 하는 값이 mid index의 값보다 작다면 mid기준으로 왼쪽에 있다는 뜻이므로, rt가 mid-1로 바뀐다
• 반복은 lt가 rt보다 작거나 같을 때만 수행해야 한다.
• 같아야하는 이유는 예를 들어, 23 32 64 75 89가 있을 때, 32를 찾아야 한다면
• 32는 mid인 64보다 왼쪽에 있으므로 lt == 0 rt == 1이 될 것이고 mid == 0이 될 것이다.
• 32는 mid==0인 값보다 오른쪽에 있으므로 lt가 mid+1이 되어 lt == 1, rt == 1이 될 것이다.
• 따라서 mid가 1이 되어 32를 찾을 수 있게된다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard