[이것이 코딩테스트다] 7. 이진 탐색

이진탐색 : 리스트 내에서 데이터를 매우 빠르게 탐색하는 탐색 알고리즘

개념

순차탐색 : 앞에서부터 타겟을 찾는 방법

                시간복잡도 = O(N)

let count = 0 ;
for (let i = 0 ; i < input.length ; i++ ){
    if (input[i] == target ) {
        count++
    }
}

---

이진탐색 :  타겟과 중간점 데이터를 반복적으로 비교해서 데이터를 찾는 방법. 정렬되지 않은 arr에는 사용할 수 없음.

                 시간복잡도 = O(log N)

                 이진탐색 구현방법 2가지(재귀함수/반복문)

**//재귀함수**
let arr = [1,4,5,9,11,15,25,33,54,82,100,111,130,157,168,219,200,224,253,298,300] ;
let target = 298;

function finding(arr, a, b) {    //a=0 , b=[arr.length-1]
    let mid = Math.floor((a+b)/2) ; //중간 index
    if (arr[mid] == target ) return mid ;
    a = target < arr[mid] ? a : mid+1 ;
    b = target < arr[mid] ? mid-1 : b ;
    **return** finding(arr,a,b) ;
}

console.log(finding(arr, 0, arr.length-1));

 >> return을 설정하지 않아서 콜스택이 쌓여 답이 undefined가 나옴

 >> 재귀함수를 사용할때는 return잘 설정하기

 >> 참고 사이트(재귀함수 사용시 주의사항): https://retriver-truck.tistory.com/54

**//반복문**
let arr = [1,4,5,9,11,15,25,33,54,82,100,111,130,157,168,219,200,224,253,298,300] ;
let target = 4;
let a = 0, b = arr.length-1 ; 
let mid 

do  {    
    mid = Math.floor((a+b)/2) ; //중간 index
    a = target < arr[mid] ? a : mid+1 ;
    b = target < arr[mid] ? mid-1 : b ;
} while (**arr[mid]** !== target) ;

console.log(mid);

// index를 변수로 줄 때는 값과 값의 index를 잘 구분지어 생각할 것. (while문 조건에 []안해서 오류남)

//반복문2
let arr = [1,4,5,9,11,15,25,33,54,82,100,111,130,157,168,219,200,224,253,298,300] ;
let target = 4;
let a = 0, b = arr.length-1 ; 
let mid , ***answer ;***

while ***(a <= b)***  {    
    mid = Math.floor((a+b)/2) ; //중간 index
    (***if (target == arr[mid]) answer = mid ; )=> 타겟을 찾는거면 있어야함.***
    a = target < arr[mid] ? a : mid+1 ;
    b = target < arr[mid] ? mid-1 : b ;
}  ;
console.log(answer);

//또는

while (a<=b) {    
    mid = Math.floor((a+b)/2) ; //중간 index
    if (arr[mid] ***<*** target) a = mid+1;  // arr[mid]==target 일때 b-1이 되어야함
    else b = mid-1;
}
console.log(a);

//두 반복문은 동일한 기능을 수행함.

// 이진 탐색을 할 때 타겟이 없는 경우(삽입할 자리를 찾기)가 있음. 그럴때는 이렇게 (a<=b) 조건을 넣으면 됨.

arr = [1,3,5,7,9]

//1) target = 3, arr[a] = 3 / target = 4, arr[a] = 5
while (a <= b) {    
    mid = Math.floor((a+b)/2) ; //중간 index
    if ***(arr[mid] < target)*** a = mid+1;
    else b = mid-1;
}

//2) target = 3, arr[b] = 3 / target = 4, arr[b] = 3
while (a <= b) {    
    mid = Math.floor((a+b)/2) ; //중간 index
    if ***(arr[mid] <= target)*** a = mid+1;
    else b = mid-1;
}

// 위는 이진 탐색에서 if 조건에 따라 달라지는 것을 설명한 것

1)의 경우 target이 arr안에 포함된다면 a = target의 index이다. 만약 포함되지 않는다면 target보다 큰 가장 가까운 수가 a가 된다.

                 예로, 4인 경우엔 a=2(값 5)이다.

2)의 경우 target이 arr안에 포함된다면 b = target의 index이다. 만약 포함되지 않는다면 target보다 작은 가장 가까운 수가 b가 된다.                      예로, 4인 경우엔 b=1(값 3)이다.

---

[예제문제] 부품찾기

전자 매장에는 부품이 N개 있고, 각 부품은 정수 형태의 고유한 번호가 있다. 부품 M개 종류가 모두 있는지 확인하는 프로그램을 작성해보자.

let input = require('fs').readFileSync('input.txt').toString().trim().split("\\n") ;

//서론
let have = +input[0];
let have_arr = input[1].split(" ").map(Number).sort();
let req = +input[2];
let req_arr = input[3].split(" ").map(Number);
let a=0, b= have-1, mid ; 

//본론 //결론
for (let i = 0 ; i < req ; i++ ){
    while (a <= b) {
        mid = Math.floor((a+b)/2) ;
        if ( have_arr[mid] < req_arr[i] ) a = mid+1 ;
        else b = mid - 1 ;
    }
    console.log(have_arr[a] == req_arr[i] ? "yes" : "no") ;
    a=0, b=have-1
}

---

[예제문제] 떡볶이 떡 만들기

한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

let input = require('fs').readFileSync('input.txt').toString().trim().split("\\n") ;

//서론
let [n, goal] = input[0].split(" ").map(Number) ;
let arr = input[1].split(" ").map(Number).sort() ;
let a=0 , b=arr[arr.length-1], mid ; 
let sum = 0 ;
let c=0 , d=arr.length-1, midmid ;

//본론 
while (a <= b) {  //첫번째 이중탐색: 자르는 길이를 이중탐색
    c=0 , d=arr.length-1, sum = 0;
    mid = Math.floor((a+b)/2) ;
    while (c <= d) {  //자를 수 있는 떡의 길이를 이중탐색
        midmid = Math.floor((c+d)/2) ;
        if ( arr[midmid] ***<*** mid ) c = midmid+1 ;
        else d = midmid - 1 ;
    }   
    for (let i = c ; i < arr.length ; i++ ){  //잘라서 합계 만들기
        sum += arr[i] - mid ;
    }
    if ( goal ***<=*** sum ) a = mid+1 ; //합이 목표보다 크면 자르는 길이를 키우기
    else b = mid - 1 ;             // 작으면 줄이기
}

//결론
console.log(***b***) ;