검색 알고리즘

알아볼 내용은 다음과 같다.

1. 정렬되지 않은 배열에서의 선형 검색
2. 정렬된 배열에서의 이진 검색
3. 나이브 문자열 검색(Naive String Search)

선형 검색 (linear search)

처음부터 끝까지 이동하면서 내가 찾는 요소인지 하나하나 확인하는 검색 방법 (순서 반대로 가능)

선형 검색의 빅오는 O(n)인데 입력인 배열의 크기가 커질수록 더 많은 검색을 해야하기 때문이다.
또한 선형 검색은 데이터가 분류되지 않았을 때 사용할 수 있는 가장 좋은 방법이다.

// 선형 검색 예시코드
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }

  return -1;
}

linearSearch([11, 27, 32, 7, 2], 2); // 4

이진 검색 (binary search)

정렬되어 있는 배열에서 찾아야할 범위를 절반씩 줄여나가면서 검색하는 방법

이진 검색의 가장 큰 특징은 값을 확인할 때마다 비교해야할 항목의 절반을 없앨 수 있다는 점이다. 맨 처음부터 전부 하나씩 확인하는 선형 검색과 비교해보면 탐색 횟수가 크게 줄어 실행 시간을 절약할 수 있다.

이진 검색을 구현하는 방법은

function binarySearch(arr, target){
  let start = 0;
  let end = arr.length - 1;
  // 1. 배열의 중간점을 선택한다.
  let middle = Math.floor((start + end) / 2);
  
  // 2. 중간점의 요소가 내가 찾는 요소인지 혹은 크거나 작은지 비교한다.
  while (arr[middle] !== target && start <= end) {
      if (target < arr[middle]) {
      	end = middle - 1;
      } else {
      	start = middle + 1;
      }
    
    // 3. 중간점의 요소가 내가 찾는 요소가 아니라면
    // 시작점과 종료점을 변경하여 중간점을 다시 구한다.
  	middle = Math.floor((start + end) / 2);
  }
 
  return arr[middle] === target ? middle : -1;
}

나이브 문자열 검색(Naive String Search)

긴 문자열(L)에서 부분 문자열(S)을 검색할 때 사용되는 검색 알고리즘

예를 들어, L에서 S가 등장하는 횟수를 구한다고 할 때 기본적인 방법으로 S를 L의 처음부터 하나씩 비교하는 것이다.

L의 처음과 S의 처음이 일치하면 L의 다음과 S의 다음을 비교해보고 또 일치하면 그 다음을 비교한다. 만약 한번이라도 일치하지 않으면 다음L로 넘어간다.

wowomgzomg
omg
   omg
      omg
         ...

이를 코드로 구현할 때는

function naiveStringSearch(long, short) {
  let count = 0;

  for (let i = 0; i < long.length; i++) {
    for (let j = 0; j < short.length; j++) {
      // j가 순회될 때 i는 비교 시작점이기 때문에 고정적이다.
      if (short[j] !== long[i + j]) break;
      
      if (j === short.length - 1) count++;
    }
  }

  return count;
}

naiveStringSearch('lorie loled', 'lol'); // 1