읽고 나면 진짜 쉬워지는 자료 구조 - 2. 이진 탐색

정렬된 리스트에서 특정 값을 빠르게 찾는 알고리즘

🔖 선형 스캔

선형 스캔이란? 그리고 장단점

• 리스트의 처음부터 끝까지 한 번에 하나씩 요소를 비교하여 목표값을 찾는 방법이다.

• 구현이 간단하고, 배열이 정렬되어 있지 않아도 사용할 수 있다는 장점이 있다.

• 다만, 배열의 크기가 크면 효율성이 떨어질 수 있으므로 이때는 다른 방법(이진탐색 등)을 고려하면 좋을듯

• 책에서도 '무식한 검사' 라고 표현한다.

JS로 구현하기

function linearSearch(arr, target) {
  for (let i = 0; i < arrr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }

  return -1;
}

시간 복잡도

• Best: 목표값이 배열의 첫 번째에 있는 경우, 한 번만 비교하면 되므로 O(1)

• Worst: 목표값이 배열의 마지막에 있거나 배열에 없는 경우, 모든 요소를 비교해야 하므로 O(N)

🔖 이진 탐색 알고리즘

이진 탐색이란?

• '정렬된' 리스트에서 목표값을 찾는 알고리즘이다. 리스트를 반으로 분할하고, 목표값이 어느 쪽 절반에 속하는지 결정한다. 이후 목표값이 포함되지 않는 절반을 버리고, 여전히 목표값이 있을 수 있는 나머지 절반만 가지고 다시 같은 과정을 반복한다. 최종적으로는 마지막 값만 남을 때까지 이를 반복한다.

• 이진 탐색의 경우, 배열이 오름차순으로 정렬되어 있음을 이용한다.

이진 탐색 수행 전 배열을 정렬해야 하는 이유

• 앞서 말했듯, 이진 탐색은 정렬된 배열에서만 올바르게 동작하는 알고리즘이다. 배열이 정렬되어 있지 않다면, 이진 탐색을 수행해도 올바른 결과를 보장할 수 없다.

• JavaScript에 내장된 sort()를 사용해 배열을 쉽게 정리할 수 있다.

JS로 구현하기

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

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

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

    if (arr[mid] === target) {
      return mid; // 목표값 찾음
    } else if (arr[mid] < target) {
      left = mid + 1; // 오른쪽 절반 탐색
    } else {
      right = mid - 1; // 왼쪽 절반 탐색
    }
  }

  return -1;
}

시간 복잡도

• sort 함수: 일반적으로 O(N log N)

• 이진 탐색: O(N log N)

• 전체: 배열 정렬과 이진 탐색을 하면 O(N log N)

🔖 선형 탐색 vs. 이진 탐색

시간 복잡도 측면

• 선형 스캔의 최악의 경우, 실행 시간은 데이터 크기에 '선형적으로' 비례한다.

• 이진 탐색은 최악의 경우라도 단계마다 데이터의 절반을 제거하기에 비교 횟수는 데이터 집합의 크기에 대해 로그적(logarithmic)이다. (e.g. N = 16일 때 최대 4번의 비교 필요 log₂16 = 4)

• 충분히 큰 리스트에 대해 원소 갯수의 로그만큼만 비교하면 된다는 이점이, 단계마다 드는 비용을 상쇄시킨다. 즉, 최악의 경우에도 데이터 크기가 증가함에 따라 (선형적에 비해) 실행 시간이 느리게 증가하여 여전히 효율적이다.