검색 알고리즘

선형 검색 (Linear Search)

미국의 주들 중 원하는 주를 찾으려면 어떻게 해야 할까?

가장 단순한 방법은 모든 주를 하나씩 순서대로 확인하면서
내가 찾는 주인지 비교해보는 것이다.

• 찾으면 true 또는 해당 인덱스 반환
• 끝까지 못 찾으면 false 또는 -1

이 방식을 선형 검색(Linear Search) 이라고 한다.

---

JavaScript에서의 선형 검색 메서드들

JavaScript에서는 우리가 직접 반복문을 돌리지 않아도,
선형 검색을 내부적으로 수행하는 메서드들이 이미 제공된다.

indexOf

['CA', 'NY', 'TX'].indexOf('NY'); // 1
['CA', 'NY', 'TX'].indexOf('FL'); // -1

• 값이 있으면 인덱스 반환
• 없으면 -1

includes

['CA', 'NY', 'TX'].includes('TX'); // true
['CA', 'NY', 'TX'].includes('FL'); // false

• 값이 있는지 존재 여부만 확인
• 결과는 true / false

find

const users = [
  { name: 'kim', age: 20 },
  { name: 'lee', age: 30 }
];

users.find(user => user.age === 30);
// { name: 'lee', age: 30 }

• 조건을 만족하는 첫 번째 요소 자체를 반환
• 못 찾으면 undefined

findIndex

users.findIndex(user => user.age === 30); // 1

• 조건을 만족하는 첫 번째 요소의 인덱스 반환
• 못 찾으면 -1

이 메서드들 모두 배열의 처음부터 끝까지 하나씩 확인한다는 점에서 선형 검색과 동일한 시간 복잡도(O(n)) 를 가진다.

시간 복잡도 (Big-O)

선형 검색의 시간 복잡도는 O(n) 이다.

• 배열이 길어질수록
• 찾는 값이 뒤에 있을수록 더 많은 비교가 필요하다.

만약 수억, 수조 번의 탐색을 선형 검색으로 처리해야 한다면
성능 문제가 생길 수 있다.

---

이진 검색 (Binary Search)

이런 상황에서 등장하는 것이 이진 검색(Binary Search) 이다.

전제 조건

정렬된 배열이어야 한다.

핵심 개념

• 분할 정복(Divide and Conquer)
  탐색 범위를 절반씩 줄여나간다

이진 검색 예제 코드

function binarySearch(arr, num) {
  arr.sort((a, b) => a - b);

  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const middle = Math.floor((left + right) / 2);

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

  return -1;
}

핵심 포인트
이진 검색은 값 비교보다 인덱스 관리가 핵심이다.
left, right 인덱스를 기준으로 탐색 범위를 계속 좁혀가는 구조

시간 복잡도

O(log n)
탐색할 때마다 확인 범위가 절반으로 줄어든다.

데이터가 많을수록 선형 검색과의 성능 차이는 극명해진다.

---

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

"wowomgzomg" 안에 "omg"가 포함되어 있는지를 확인한다고 해보자.

가장 단순한 방법은
긴 문자열을 한 글자씩 이동하며 "omg"의 첫 글자부터 비교하는 것이다.

이 방식을 나이브 문자열 검색이라고 한다.

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

  for (let i = 0; i <= long.length - short.length; i++) {
    let match = true;

    for (let j = 0; j < short.length; j++) {
      if (long[i + j] !== short[j]) {
        match = false;
        break;
      }
    }

    if (match) count++;
  }

  return count;
}

시간 복잡도

O(n × m)

n: 긴 문자열 길이
m: 찾는 문자열 길이

문자열이 길어질수록, 패턴이 길어질수록 성능이 급격히 떨어진다.