[이진탐색]입국심사

[이분탐색 범위 개념 잡기]

 

이분탐색시 종료조건이 while(left<right)가 아니라 왜 while(left<=right)일까?

 => 찾고자 하는 값(n)이 left 혹은 right인 경우의수를 포함하기 위해서다.

 

 만약 while(left<right)로 선언한다면, 우리는left mid(==left+1) right(==left+2) 인 시점에 종료가된다.

 이때 가장 정답에 가까운 mid 값을 얻을 수 있으나, left 혹은 right가 정답이라면 오류가 발생한다.

 따라서 배열의 모든 값들에 대하여 이분탐색을 구현하기 위해선 while(left<=right)로 선언해야 한다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;

    long long left = 1;
    long long right = *max_element(times.begin(),times.end())*n;
    //이분 탐색 진행.
   

    while(left<=right)
    {
         long long mid=(left+right)/2;
        long long person = 0;

        for(int time : times)
        {
            person+=mid/time;
            if(person>=n) break;
        }

        if(person>=n)
        {
            answer=mid;
            right=mid-1;
        }
        else
        {
            left=mid+1;
        }

    }
    return answer;
}