검색 알고리즘 이해하기: 선형 검색과 이진 검색의 원리와 JavaScript 예제

검색 알고리즘은 주어진 데이터 집합에서 원하는 값을 찾는 과정을 시스템적으로 정리한 절차입니다.

두 가지 대표적인 검색 알고리즘인 선형 검색과 이진 검색에 대해 원리와 함께 JavaScript 예제를 통해 알아보겠습니다.

선형 검색 (Linear Search)

선형 검색은 가장 간단한 검색 알고리즘입니다. 주어진 데이터 집합의 처음부터 끝까지 순차적으로 원하는 값을 찾는 방법입니다. 

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

const arr = [5, 3, 9, 1, 7];
const target = 9;
const index = linearSearch(arr, target);

console.log(`Target ${target} found at index ${index}`);

 

이진 검색 (Binary Search)

이진 검색은 정렬된 데이터 집합에서 원하는 값을 찾는 효율적인 검색 알고리즘입니다. 

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

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

    if (arr[mid] === target) {
      return mid;
    }

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

const sortedArr = [1, 3, 5, 7, 9];
const target = 7;
const index = binarySearch(sortedArr, target);

console.log(`Target ${target} found at index ${index}`);

이진 검색은 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이기 때문에, 데이터의 정렬 상태에 따라 적합한 검색 알고리즘을 선택하는 것이 중요합니다. 선형 검색은 정렬되지 않은 데이터 집합에서도 사용할 수 있지만, 이진 검색은 효율성 측면에서 정렬된 데이터 집합에서 더 빠르게 검색을 수행할 수 있습니다.