검색(서칭) 알고리즘

서칭 알고리즘은 데이터 내에서 조건을 만족하는 값을 찾을 때 사용되는 알고리즘 패턴이다.
이러한 검색 알고리즘에는 여러 종류가 있다.

선형 검색 알고리즘

선형 알고리즘은 각 값을 하나 씩 확인하는 패턴으로, 자바스크립트에는 이미 해당 패턴을 사용한 메서드(indexOf, includes 등)가 존재한다. 첫 번째 값부터 마지막 값까지 찾으려는 값을 찾을 때까지 계속해서 조건을 비교하는 패턴이다.

가장 간단한 패턴이지만, 데이터가 많을 경우 비효율적(O(n))일 수 있다.

/**
 *
 * @param {number[]} arr
 * @param {number} num
 * @returns number
 */
function linearSearch(arr, num) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === num) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearch([10, 15, 20, 25, 30], 15)); // 1
console.log(linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4)); // 5
console.log(linearSearch([100], 100)); // 0
console.log(linearSearch([1, 2, 3, 4, 5], 6)); // -1
console.log(linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 10)); // -1
console.log(linearSearch([100], 200)); // -1

이진 검색 알고리즘

이진 검색 알고리즘은 정렬된 데이터에서 사용 가능한 알고리즘 패턴으로, 선형 검색 알고리즘에 비해 개선된 패턴이다.

분할 정복을 사용한 검색 알고리즘이다. 먼저 데이터의 중간 값을 구하고, 찾아야 하는 값이 중간 값보다 크면, 앞의 데이터를 소거하고 뒤의 데이터를 가진다. 그리고 남은 데이터로 찾아야 하는 값을 찾을 때까지 계속 반복 수행한다.

/**
 *
 * @param {number[]} arr
 * @param {number} num
 * @returns number
 */
function binarySearch(arr, num) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let center = Math.floor((left + right) / 2);

    if (arr[center] === num) {
      return center;
    } else if (arr[center] > num) {
      right = center - 1;
    } else if (arr[center] < num) {
      left = center + 1;
    }
  }
  return -1;
}

이진 검색 알고리즘의 시간 복잡도는 최악의 경우에도 O(log n)이다

naive string search

naive string search는 문자열에서 특정 패턴을 가진 문자열을 찾는 데에 사용되는 패턴이다.

문자열을 순회하면서 각 문자열이 패턴과 일치하는지 검사한다. 패턴과 일치하지 않는 문자열이 포함되어 있다면 다시 새롭게 검색을 시작한다. 만약 모든 문자열이 일치(j가 pattern의 길이와 같아짐)할 경우, 패턴을 찾은 것이다.

/**
 *
 * @param {string} str
 * @param {string} pattern
 */
function naiveStringSearch(str, pattern) {
  let answer = 0;
  for (let i = 0; i < str.length; i++) {
    for (let j = 0; j < pattern.length; j++) {
      if (pattern[j] !== str[i + j]) {
        break;
      } else if (j === pattern.length - 1) {
        answer += 1;
      }
    }
  }
  return answer;
}