JavaScript로 이진 탐색(Binary Search) 알고리즘 구현하기

안녕하세요! 이번에는 JavaScript를 사용하여 이진 탐색(Binary Search) 알고리즘을 구현하는 방법에 대해 알아보겠습니다. 이진 탐색은 정렬된 배열에서 특정 요소를 빠르게 찾는 알고리즘으로, 배열을 반으로 나누어 탐색 범위를 줄여가며 원하는 요소를 찾아내는 효율적인 방법입니다.

자, 그럼 바로 시작해봅시다!

1. 이진 탐색 알고리즘 구현하기

 

아래의 JavaScript 코드는 이진 탐색 알고리즘을 구현한 예시입니다. 주어진 배열에서 특정 요소(target)를 찾는 함수를 구현하였습니다.

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

  while (left <= right) {
    let 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; // 요소가 배열에 없는 경우 -1 반환
}

2. 이진 탐색 알고리즘 사용하기

 

이제 위에서 구현한 이진 탐색 알고리즘을 사용하여 배열에서 요소를 찾아내는 예시를 살펴보겠습니다.

const arr = [2, 4, 7, 10, 13, 18, 22, 27];
const target = 13;

const result = binarySearch(arr, target);
if (result !== -1) {
  console.log(`요소 ${target}을(를) 찾았습니다. 인덱스: ${result}`);
} else {
  console.log(`요소 ${target}을(를) 찾지 못했습니다.`);
}

위의 코드에서는 주어진 정렬된 배열 arr에서 target인 13을 찾는 예시입니다. binarySearch() 함수를 호출하고 반환된 인덱스를 확인하여 요소를 찾았는지 여부를 출력합니다.

 

3. 시간 복잡도 분석

 

이진 탐색은 배열을 반으로 나누어 탐색 범위를 절반씩 줄여나가므로 시간 복잡도는 O(log n)입니다. 이는 매우 효율적인 알고리즘으로, 큰 크기의 정렬된 배열에서도 빠른 탐색이 가능합니다.

 

이진 탐색 알고리즘을 사용하면 탐색 속도를 크게 향상시킬 수 있으므로, 정렬된 배열에서 특정 요소를 찾아야 하는 상황에서 유용하게 활용할 수 있습니다.

이제 JavaScript로 이진 탐색(Binary Search) 알고리즘을 구현하는 방법에 대해 알아보았습니다. 이진 탐색은 프로그래밍에서 자주 사용되는 중요한 알고리즘 중 하나입니다.