Binary Search Explanation

Problem Summary

Implement binary search to find a target in a sorted array. Return the index or -1 if not found.

Detailed Explanation

이 문제는 **이진 탐색(Binary Search)** 알고리즘을 학습합니다. 정렬된 배열에서 O(log n) 시간에 원소를 찾는 효율적인 방법입니다. **이진 탐색의 핵심 원리** 정렬된 배열에서 중간값을 확인하고, 찾는 값이 중간값보다 크면 오른쪽 절반, 작으면 왼쪽 절반만 탐색합니다. 매 단계마다 탐색 범위가 절반으로 줄어듭니다. **알고리즘 단계** 1. left=0, right=length-1로 시작 2. mid = (left + right) / 2 계산 3. arr[mid]와 target 비교: - 같으면: mid 반환 (찾음!) - target이 크면: left = mid + 1 - target이 작으면: right = mid - 1 4. left > right이면 종료 (없음) **[1,2,3,4,5]에서 3을 찾는 과정** - left=0, right=4, mid=2 - arr[2]=3 === target → 반환 2 **[1,2,3,4,5]에서 6을 찾는 과정** - left=0, right=4, mid=2: 3<6 → left=3 - left=3, right=4, mid=3: 4<6 → left=4 - left=4, right=4, mid=4: 5<6 → left=5 - left=5, right=4: left>right → -1 반환 **선형 탐색 vs 이진 탐색** - 선형 탐색: O(n) - 100만 개면 최대 100만 번 - 이진 탐색: O(log n) - 100만 개도 약 20번이면 충분

Solution Code

solution.js

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;
}

Key Concepts from This Problem

1. 이진 탐색 알고리즘

2. left/right 포인터

3. 분할 정복

4. O(log n) 시간복잡도

Common Mistakes

✗ while 조건이 left < right면 마지막 요소를 놓칠 수 있습니다 (left <= right 사용)

✗ mid 계산 시 정수 나눗셈을 위해 Math.floor가 필요합니다

✗ 배열이 정렬되어 있지 않으면 이진 탐색이 작동하지 않습니다

Hints

Hint 1: left, right 포인터를 사용하세요.

Hint 2: 중간값과 target을 비교합니다.

Hint 3: target이 크면 left = mid + 1, 작으면 right = mid - 1

Complexity Analysis

Time Complexity

O(log n)

Grows slowly even with larger input

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #이진탐색 #분할정복