탐색 알고리즘 - 이진 탐색

이진 탐색(Binary search)

• 전체 배열에서 가운데에 존재하는 원소의 값과 비교하여 다음 탐색 위치를 결정하는 알고리즘.
• 순차 탐색과 달리 배열의 원소들이 커지는 순서대로 정렬이 되어 있어야 하는 조건이 있다.
  
  

탐색 방법

• 자료의 집합에서 n/2 번째 원소가 찾으려는 값과 일치하는지 비교한다.
• 찾는 값이 원소의 값 보다 크면 (n/2) + 1 번째 부터 n번째 까지 이진 탐색 수행
  찾는 값이 원소의 값 보다 작으면 1번째 부터 (n-1) / 2번째 까지 이진 탐색 수행
• 값과 일치하는 원소가 아니라면 위 과정을 반복하며 일치하는 값이 몇 번재 원소인지 반환.
• 마지막까지 비교하였으나 일치하는 값의 원소가 존재하지 않으면 원소가 없다고 판단한다.
  
  

특징

• 비교횟수
  최선의 경우 : 1
  평균의 경우 : (log2^n + 1) / 2
  최악의 경우 : log2^n + 1 (n/2, n/4, n/8, ...)
  
  시간 복잡도 : O(log N)

• 자료가 정렬되어 있어야 한다.

• 자료가 커지면 커질수록 탐색이 효율적이다.

• 알고리즘이 복잡하지만 속도가 빠르다.

구현

배열을 이용한 이진 탐색 구현

function BinarySearch(arr, data) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = parseInt((low + high) / 2);

    if (arr[mid] > data) high = mid - 1;
    else if (arr[mid] < data) low = mid + 1;
    else return mid;
  }

  return -1;
}

function Solution() {
  const arr = [
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28,
  ];

  const findData = 14;
  const findIdx = BinarySearch(arr, findData);

  if (findIdx !== -1) {
    console.log(`탐색 결과 : ${findIdx + 1}번째에 원소가 존재합니다.`);
  } else {
    console.log(`탐색 결과 : 원소가 존재하지 않습니다.`);
  }

  return;
}

Solution();

이진 탐색 트리를 활용한 이진 탐색 구현

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

class BinarySearchTree {
  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 (value === currentNode.value) return;

      // 추가되는 값이 루트 보다 크면 오른쪽 서브트리
      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;
  }
}

const tree = new BinarySearchTree();

tree.insert(5);
tree.insert(4);
tree.insert(7);
tree.insert(8);

console.log(tree.has(7)); // true
console.log(tree.has(1)); // false