TIL 45일차_알고리즘_이진탐색트리

이진탐색트리

단순탐색의 시간복잡도는 O(N),
이진탐색의 시간복잡도는 O(logN)이다.
따라서 N의 크기가 커질수록 이차이는 커진다.

예를들어 40억개를 탐색하면
단순탐색은 40억번을 계산해야하고
이진탐색은 32번만 계산하면된다.

배열에서 특정숫자를 찾는 이진탐색은 다음과같다.

function bst(list,item){
    let min = 0
    let max = list.length-1;


    while(min<=max){ 
        let mid = Math.floor((min+max)/2);

        if(item === list[mid]) return mid;
        else if(item < list[mid]){
            max = mid-1;
        }else{
            min = mid+1;
        }
    }
return null
}