이진탐색(파라메트릭 서치)

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

1. 이진탐색
   1-1 이진탐색 배열

정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
O(log n)만큼 시간복잡도가 걸린다.

실사용예시

• 업/다운 게임

비교 : 선형탐색
순서대로 하나씩 찾는 탐색 알고리즘 O(n) 시간복잡도가 걸린다.

1-2 이진 탐색 트리

이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

이진탐색트리의 문제점

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

=> 코테에서는 주로 이진 탐색 배열로만으로 푸는 문제가 대부분.

2. 특징

• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• O(log n) 시간복잡도인 만큼 상당히 빠르다.

=> 이렇게 빠른 알고리즘은 거의 없다.

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;
}

3. 코테
   핵심키워드 : 전체 리스트에서 특정 구간을 찾아야하는 경우, 모든 요소 중 X를 만족하는 가장 큰/작ㅇ느 값을 만족하는 지점, 커트라인
   참고상황 : 제한 조건이 빡세서 O(log(n)) 시간복잡도 적용이 필요시
   대표문제: 입국 심사 문제