2.8Searching Algorithms

JavaScript에는 배열이나 문자열에서 특정 값을 찾기 위한 다양한 검색 메소드가 있다.

• indexOf
• includes
• find
• findIndex

이번 포스팅에선 이들 메소드들의 동작 원리를 바탕으로 직접 검색 알고리즘을 구현해보자.

Linear Search(선형 탐색)

모든 요소를 앞에서부터 순서대로 하나씩 비교하며 찾는 방법이다.

indexOf를 쓰지 말고 배열과 값을 받아 값이 존재한다면 해당 값이 어디에 있는지 인덱스를 반환하는 함수를 직접 구현해보자.

javascript
linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4) // 5
linearSearch([100], 100) // 0
linearSearch([1,2,3,4,5], 6) // -1

이런 식으로 O(n)의 시간 복잡도를 가지는 함수가 된다.

javascript
function linearSearch(arr, val){
  for(let i = 0; i < arr.length; i++){
    if(arr[i] === val) return i;
  }
  return -1;
}

Binary Search(이진 탐색)

정렬된 배열에서 한 번에 남은 요소의 절반씩을 제거하며 찾는 방법이다.

이 방식은 Divide and Conquer를 활용한 것이다. 정렬된 배열에서, 절반에 있는 지점에 있는 요소보다 검색하는 요소가 큰지 작은지를 계속 반복하면서 요소의 정확한 위치를 찾을 수 있다.

javascript
function binarySearch(arr, val){
  let start = 0;
  let end = arr.length -1;
  let middle = Math.floor((start + end) / 2);

  while(arr[middle] !== val && start <= end){
    if(val < arr[middle]) end = middle - 1;
    else start = middle + 1;
    middle = Math.floor((start + end) / 2);
  }
  return arr[middle] === val ? middle : -1;
}

이 방식은 전체 배열을 각 단계별로 반으로 줄여가며 작업하는 것이기 때문에 배열의 길이 n을 2를 밑으로 하는 log n만큼의 단계로 검색을 하는 O(log n)의 시간 복잡도를 가진다.

Naive String Search(단순 문자열 탐색)

긴 문자열에서 짧은 문자열이 부분적으로 몇번 나오는지 확인하는 함수를 만든다고 하자. 문자열의 각 위치에서 짧은 문자열과 일치하는지 한 글자씩 비교한다.

javascript
function naiveSearch(long, short){
  let count = 0;
  for(let i = 0; i < long.length; i++){
    for(let j = 0; j < short.length; j++){
      if(short[j] !== long[i + j]){
        break;
      }
      if(j === short.length - 1){
        count++;
      }
    }
  }
  return count;
}