[TIL 6] 이진 탐색 in js

이진탐색

업다운 문제와 같다.

이진 탐색의 특징

• 반드시 정렬이 되어 있어야 사용 가능
• 배열 혹은 이진 트리를 이용해 구현할 수 있다
• O(logn) 시간 복잡도이기 때문에 엄청 빠르다!

=> 코테에 자료가 1,000,000,000개 정도가 나오면 이진 탐색이라고 볼 수 있다.

이진 탐색 구현

배열로 구현 시 중간에 삽입, 삭제 시 선형시간이 걸리는 단점!
하지만 이진 탐색 트리는 추가, 삭제 모두 O(logn)시간이 걸린다!

이진 트리 요소 추가

• 루트보다 작으면 왼쪽, 크면 오른쪽으로 삽입
  같으면 상관 없음

요소 삭제

• 리프 노드를 삭제하는 경우에는 별다른 처리 없이 부모 정점에서 끊으면 됨
• 하나의 서브 트리를 가지는 경우 제거되는 정점의 부모 간선을 자식 정점을 가리키게 바꾸면 됨.
• 두 개의 서브 트리를 가지는 경우
  왼쪽 서브 트리의 가장 큰 값 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 된다.
  이 경우 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체한다.

이진 탐색 트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
• 그런 경우 순차 탐색과 동일한 시간 복잡도를 가진다
• 이를 해결하기 위해 다음과 같은 자료구조를 이용할 수 있다

=> AVL 트리, 레드 블랙 트리

코테에서는 삽입, 삭제가 이뤄지지 않는다면 구현이 쉬운 배열을 이용하는 것이 좋음!! 배열을 이용하는 경우가 훨씬 많을 것!!

AVL 트리는.. 참고로 데이터베이스를 배울 때 구현이 최종 과제 였는데, 엉망으로 제출했다고 한다..ㅋㅋㅋㅋㅋㅋ^^

코테에 자주 사용하는 배열 이진 탐색을 구현해 보자!

• 이진 탐색은 최적값을 구하는 문제에 많이 나온다. 처음에는 최적값이라고 해서 그리디나 다른 문제로 생각했는데, 이진 탐색이라는 것을 알고 신기했다. 이게 바로 경험이 부족한 탓..ㅠㅠ

const array = [1, 1, 5, 134, 400, 599, 1004, 2876, 8712];
function binarySearch(array, findValue){
    let left = 0;
    let right = array.length - 1;
    let mid = Math.floor((left + right) / 2);

    while(left <= right){
        if(array[mid] === findValue)
            return mid;
        if(array[mid] < findValue)
            left = mid + 1;
        else
            right = mid - 1;

        mid = Math.floor((left + right) / 2);
    }
    return -1;
}

for(let i =0; i < array.length; i++){
    console.log(binarySearch(array, array[i]));
} // 1 1 2 3 4 5 6 7 8

결정 문제
최솟값 구하기, 최적 구하기

• 결정문제 = 이진탐색 = 파라메트릭 서치
  이진 탐색 너무 어려운 것...

프로그래머스 입국 심사 다시 혼자 식 세워서 풀어보기!!