이진 탐색 (Binary Search) 설명과 JavaScript 예제

이진 탐색(Binary Search)은 정렬된 배열에서 중간값을 기준으로 탐색 범위를 절반으로 줄여가며 원하는 값을 찾는 고속 탐색 알고리즘입니다. 정렬된 데이터에 한해 사용할 수 있지만, 시간 복잡도가 O(log n)으로 매우 뛰어난 성능을 자랑합니다.

---

1. 동작 원리

1. 배열의 중간값을 구함
2. 중간값과 찾는 값을 비교
   • 같으면 인덱스 반환
   • 작으면 오른쪽 절반 탐색
   • 크면 왼쪽 절반 탐색
3. 탐색 범위를 좁혀가며 반복
4. 찾지 못하면 -1 반환

---

2. JavaScript 예제

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

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

    if (midVal === target) return mid;
    else if (midVal < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)); // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 4)); // -1

• Math.floor()를 사용해 중간 인덱스를 계산
• 반복문 안에서 좌우 범위를 줄여가며 탐색

---

3. 성능 분석

구분	시간 복잡도
최선의 경우	O(1)
평균	O(log n)
최악의 경우	O(log n)

• 공간 복잡도는 O(1) (반복문 기반)
• 재귀를 사용할 경우 O(log n)의 스택 공간이 필요함

---

4. 이진 탐색의 특징

• 반드시 정렬된 배열이어야 함
• 매우 빠른 탐색 속도 → 대규모 데이터에 적합
• 삽입/삭제 연산이 자주 발생하는 구조에서는 효율 저하 가능

---

마무리

이진 탐색은 탐색 알고리즘 중 가장 널리 쓰이며 실전에서도 매우 유용한 기법입니다. 단, 정렬된 배열이 선행 조건이기 때문에 이 점을 반드시 고려해야 합니다. 상황에 따라 선형 탐색과 적절히 구분하여 사용하는 것이 중요합니다.

알고리즘 학습뿐 아니라 실무에서도 자주 사용되는 기본 탐색 방법입니다.