[자료구조] 이진 탐색(Binary Search)

2022년 05월 10일

이진 탐색(Binary Search)

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

이진 탐색의 특징

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

배열로 이진 탐색 구현

const array = [1, 1, 2, 5, 123, 400, 595, 1004, 2331];

function binarySearch(array, findValue) {
  let left = 0;
  let right = array.lenght - 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; // 만약 루프를 빠져나오지 못했을 경우 -> 요소를 찾지 못한 것
}

배열로 이진 탐색을 구현한 경우 요소 삭제 및 삽입 시 선형 시간 복잡도 O(n)를 걸리게 되는 단점이 존재한다.

이진 탐색 트리로 구현

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode; // 루트가 비어있을 경우 새로 추가한 값이 루트가 되고 종료 됨
      return;
    }

    let currentNode = this.root;
    while (currentNode !== null) {
      if (currentNode.value < value) {
        if (currentNode.right === null) {
          currentNode.right = newNode;
          break;
        }
        currentNode = currentNode.right;
      } else {
        if (currentNode.left === null) {
          currentNode.left = newNode;
          break;
        }
        currentNode = currentNode.left;
      }
    }
  }

  has(value) {
    let currentNode = this.root;
    while (currentNode !== null) {
      if (currentNode.value === value) return true;

      if (currentNode.value < value) {
        currentNode = currentNode.right;
      } else {
        currentNode = currentNode.left;
      }
    }

    return false;
  }
}