검색 알고리즘 - 이진 검색의 이해와 효율적 구현 방법

이진 검색 개요

• 정렬된 배열에서 원하는 요소를 효율적으로 찾습니다.
• 배열의 중간 값과 목표 값을 비교하여 검색 범위를 절반씩 줄여나갑니다.

이진 검색 동작 원리

1. 배열의 중간 인덱스를 계산합니다.
2. 중간 값과 목표 값을 비교합니다.
3. 같을 경우 중간 인덱스를 반환합니다.
4. 중간 값이 목표 값보다 작으면 우측 부분에서 검색을 계속합니다.
5. 중간 값이 목표 값보다 크면 좌측 부분에서 검색을 계속합니다.
6. 검색 범위가 0이 되면 목표 값이 없는 걸로 간주하고 -1을 반환합니다.

이진 검색 코드 예

function test(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
  } else if(arr[mid] < target) {
   left = mid + 1
  } else {
   right = mid - 1
  }
 }
 return -1
}

const arr = [5,4,3,2,1]
const target = 3
test(arr, target)

• 중간 값이 목표값보다 작으면 우측 부분만 탐색하기 위해서 left의 값을 중간값 + 1로 합니다.
• 중간 값이 목표값보다 크면 좌측 부분만 탐색하기 위해서 right의 값을 중간값 - 1로 합니다.

이진 검색 시간 복잡도

• 최선(목표 값이 중간 값인 경우) : O(1)
• 평균과 최악의 경우 : O(log n)

이진 검색 장점

• 시간 복잡도가 O(log n)으로 효율적입니다.
• 배열의 크기가 커질수록 선형 검색보다 훨씬 빠른 성능을 보입니다.

이진 검색 단점

• 정렬되지 않은 배열에서는 사용할 수 없습니다.

이진 검색 활용

• 정렬된 큰 크기의 데이터에서 특정 값을 빠르게 찾아야 하는 경우 유용합니다.
  • 데이터 파일 인덱싱
  • 파일 시스템 검색
  • 압축 알고리즘
  • 암호화 알고리즘