알고리즘 - Search(탐색)

탐색 알고리즘

자바스크립트에선 탐색을 지원하는 많은 기능을 제공하고 있다. 탐색 알고리즘은 그 기능들이 어떻게 돌아가는지 어떤게 효율적인 방법인지 알 수 있다.

Linear Search(선형 탐색)

주어진 배열의 모든 요소들을 탐색하며 원하는 요소와 일치하는지 찾는 방법. 정렬되지 않는 배열을 탐색할 때 사용하는 방법이기도 하다. 자바스크립트의 indexOf, includes, find, findIndex 등 많은 메소드들이 이런식으로 동작한다.

//선형탐색 예시
//주어진 배열을 탐색하여 주어진 값과 일치하는 경우 인덱스를 리턴하고 없는 경우 -1을 리턴한다.
function solution(arr, n) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === n) return i;
  }
  return -1;
}

solution([1, 3, 4, 5], 2);

선형탐색은 주어진 배열을 모두 탐색하며 찾는 방법이기 때문에 주어진 데이터의 길이에 따라 빅오가 결정된다. 최선의 방법은 O(1) 이고 최악의 방법은 O(n)이기 때문에 평균적인 빅오는 O(n)이다.

Binary Search(이진 탐색)

이진탐색은 정렬된 배열에만 적용 가능한 탐색방법으로 기준에 따라 제거하고 남은 요소들 중 반만 탐색 때문에 다른 탐색 유형보다 빠르다.

//이진탐색 예시
//정렬된 배열과 값을 받는 함수를 작성하라

//1. 배열의 시작인 left pointer와 배열의 끝인 right pointer를 생성한다
//2. 가운데인 pointer를 생성한다.
//3. 원하는 값을 찾은 경우 해당 인덱스를 리턴한다.
//4. 값이 너무 작은 경우, left pointer를 업한다.
//5. 값이 너무 큰 경우, right pointer를 다운한다.
//6. 일치하는 값이 없는 경우 -1을 리턴한다.

function solution(arr, n) {
  let left = 0,
    right = arr.length - 1,
    middle = Math.floor((left + right) / 2);

  while (arr[middle] !== n && left <= right) {
    if (n < arr[middle]) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
    middle = Math.floor((left + right) / 2);
  }
  if (arr[middle] === n) return middle;
  return -1;
}

solution([1, 3, 5, 7, 9, 11], 8);

이진탐색의 시간복잡도를 보면 최악의 경우와 평균적인 경우에는 O(log n), 최선의 경우에는 O(1)이다.

Naive String Search

긴 문자열에서 작은 문자열이 몇개 있는지 찾는 알고리즘 문제.

//1. 주어진 긴 문자열을 반복한다
//2. 주어진 짧은 문자열을 반복한다
//3. 각 문자가 일치하지 않으면 내부 반복문은 멈춘다
//4. 각 문자가 일치하면 계속한다
//5. 내부 반복문이 완료되고 일치하는 것을 찾으면 일치하는 걸 세는 카운트를 증가한다
//6. 5에서 증가한 것을 리턴한다

function solution(long, short) {
  let answer = 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) answer++;
    }
  }
  return answer;
}

solution("sklsdsklwowo", "wo");