탐색: 이진 탐색

 

이진 탐색이란?

이진 탐색(Binary Search)은 정렬된 데이터 집합에서 효율적으로 특정 값을 찾는 알고리즘입니다. 중앙값을 기준으로 데이터를 반으로 나누어가며 탐색 범위를 절반씩 줄여나가는 방식으로 작동합니다. 이 과정은 찾고자 하는 값이 발견되거나 탐색 범위가 더 이상 없을 때까지 반복됩니다.

 

이진 탐색의 작동 원리

이진 탐색은 정렬된 배열에서 중앙에 위치한 요소를 찾고, 그 요소가 찾고자 하는 값인지 확인합니다. 찾고자 하는 값이 중앙값보다 작으면 왼쪽 부분을, 크면 오른쪽 부분을 새로운 탐색 범위로 선택하여 같은 과정을 반복합니다.

 

이진 탐색의 단계별 과정

1. 정렬된 데이터 집합의 최소 인덱스(min)와 최대 인덱스(max)를 정합니다.
2. 현재 탐색 범위의 중앙 인덱스(mid)를 계산합니다.
3. 중앙값과 찾고자 하는 값(target)을 비교합니다.
   • target이 중앙값보다 작으면, max를 mid - 1로 조정합니다.
   • target이 중앙값보다 크면, min을 mid + 1로 조정합니다.
   • target이 중앙값과 동일하면, 탐색을 종료하고 mid를 반환합니다.
4. min > max가 될 때까지 위의 과정을 반복합니다. 찾고자 하는 값이 없는 경우, 탐색 실패를 나타내는 값을 반환합니다.

이진 탐색의 복잡도

시간 복잡도: O(log n)으로, n은 데이터 집합의 크기입니다.
공간 복잡도: O(1)로, 추가적인 메모리 공간이 필요 없습니다.

---

Pseudocode

function binarySearch(arr, target) {
  let min = 0
  let max = arr.length - 1

  while (min <= max) {
    let mid = Math.floor((min + max) / 2)
    if (arr[mid] == target) {
      return mid
    } else if (arr[mid] < target) {
      min = mid + 1
    } else {
      max = mid - 1
    }
  }
  return -1 // 탐색 실패
}

 

실제 예시로 이해하기

예를 들어, [3, 6, 8, 12, 15, 18, 20, 22, 26, 29] 배열에서 값 15를 찾고자 한다고 가정해봅시다.

1. 초기 min = 0, max = 9로 설정합니다.
2. 첫 번째 탐색에서 mid = 4이며, arr[4] = 15입니다.
3. 찾고자 하는 값이 중앙값과 일치하므로 인덱스 4를 반환하고 탐색을 종료합니다.

이진 탐색은 정렬된 데이터에서 빠른 탐색 속도를 제공합니다. 큰 데이터 집합에서 원하는 값을 효율적으로 찾고자 할 때 매우 유용한 탐색 방법입니다.