이분탐색 알고리즘

개요

O(lgN):로그시간 연산횟수가 logN에 비례해서 증가하면 O(lgN)이 된다. (ex) 이진탐색
func6(k, arr, left, right){
if(left>rigth) return -1;
m=(left+right)/2;
if(arr[m]==k) return m;
else if(arr[m]>k) return func6(k,arr,left,m-1);
else return func(k,arr,m+1,right);
}

예제

프로그래머스 입국심사 lv3

times의 모든 요소를 n을 곱해

새로운 배열 n에 넣고 이를 정렬하여 n번째 요소를 찾으면 된다고 생각하였다.

function solution(n, times) {
    var answer =0;
		var arr=[];
    times.sort((a,b)=>a-b)
    times.map((iter)=>{
        for(var i=1;i<=n;i++){
            arr.push(i*iter);
        }
    })
    arr.sort((a,b)=>a-b)
    return arr[n-1];
    
}

⇒ 위의 방식 대로 풀면 코드는 간단하지만 시간초과 or signal dump가 뜬다.

이분탐색을 사용한 수정 코드

function solution(n, times) {
    times.sort((a,b)=>a-b)
    var answer = times[times.length-1]*n;
    var left=1;
    var right=answer;
    var arr=[];
    
    while(left<=right){
        var mid=Math.floor((left+right)/2);
        var sum=0;
        for(var i=0;i<times.length;i++){
            sum+=Math.floor(mid/times[i]);
            
        }
        if(sum<n){
            left=mid+1;
        } else {
            answer=Math.min(answer,mid);
            right=mid-1;
        }
        
    }
    return answer;
    
}