자바스크립트 검색 알고리즘 1 : Linear Search, Binary Search

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

앞서 정렬 알고리즘에 대해서 살펴봤다면, 이번에는 모든 노드들을 traversing하면서 검색하는 알고리즘에 대해서 살펴보자. 검색은 실생활에서 아주 많이 사용되는 기능이기 때문에 잘 살펴보자.

 

1. Linear Search

가장 단순하지만, 동시에 가장 비효율적인 검색 알고리즘이다. 단순히 list를 특정 값을 찾을 때까지 loop over하는 작업이다. 검색을 시작하자마자 찾게 되는 Best Case에서는 O(1)이지만, 가장 마지막에 찾게되는 Worst Case에는 O(n)이다.

 

☞ Linear Search 로직

 

자바스크립트에 내장된 배열 메소드인 indexOf, findIndex, find, includes 같은 메소드는 모두 내부적으로 linear searching을 사용하고 있다. O(n)은 그렇게 나쁜 것은 아니지만, 구글이나 페이스북 같이 검색해야 하는 정보의 양이 방대할 경우 많은 시간과 비용을 소모할 수 있다.

 

2. Binary Search(이진 검색)

만일 찾고자 하는 데이터의 값이 정렬되어 있다면, O(n)에서 개선될 수 있을까? 이 경우, 우리는 Binary Search를 사용할 수 있다. 왜냐하면 이미 정렬된 배열의 midpoint를 기준으로 찾고자하는 값이 포함되지 않은 반대쪽 절반을 덜어낼 수 있기 때문이다. 

// [1, 3, 4, 9, 12, 34, 45]에서 34를 찾고자 할 경우, 
// midpoint인 9를 기준으로 34가 9보다 큰지 작은지를 판단하고,
// 크기 때문에 앞쪽 배열 절반은 날릴 수 있다.
[9, 12, 34, 45]

// 남은 배열에서 다시 중간값을 찾고 같은 과정을 반복한다.
[12, 34, 45]

// 그리고 midpoint를 찾는 순간 34를 찾게 됐다.
// O(n)으로 one by one 찾는 대신 3번의 operation으로 원하는 결과를 찾았다.

 

이렇게 Binary Search로 절반을 버려가며 검색하는 방식의 시간 복잡도는 O(log n)이다. Divide and Conquer를 활용하기 때문이다. 따라서 O(n)보다 훨씬 개선된 성능을 보여줄 수 있다.

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

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  lookup(value){
    if (!this.root) {
      return false;
    }
    let currentNode = this.root;
    while(currentNode){
      if(value < currentNode.value){
        currentNode = currentNode.left;
      } else if(value > currentNode.value){
        currentNode = currentNode.right;
      } else if (currentNode.value === value) {
        return currentNode;
      }
    }
    return null
  }
}