이진 탐색 (Binary Search)

전화번호부에서 “홍길동”을 찾는다고 상상해보세요. 처음부터 하나씩 넘기지 않고, 중간쯤 펴서 확인한 다음 앞쪽 또는 뒤쪽으로 이동하죠?

이것이 바로 이진 탐색입니다!

저도 처음에는 “왜 이게 빠른 거지?”라고 의문이었는데, 실제로 1,000,000개의 데이터에서 단 20번의 비교로 원하는 값을 찾는 것을 보고 깜짝 놀랐습니다.

왜 이진 탐색을 배워야 할까요?

1. 엄청난 성능 향상

// 1,000,000개의 데이터에서 검색
// 선형 탐색: 평균 500,000번 비교
// 이진 탐색: 최대 20번 비교

// 25,000배 빠릅니다! 🚀

2. 실무에서 매우 자주 사용

데이터베이스 인덱스
파일 시스템
자동완성 기능
게임 AI (A* 알고리즘의 기초)

3. 많은 문제의 기초

이진 탐색을 이해하면 다음을 배우기 쉽습니다.

이진 탐색 트리 (BST)
분할 정복 알고리즘
최적화 문제

⚠️ 중요한 전제조건

이진 탐색은 정렬된 배열에서만 동작합니다!

// ❌ 정렬 안 됨 - 이진 탐색 불가
const unsorted = [5, 2, 8, 1, 9];
binarySearch(unsorted, 8);  // 잘못된 결과!

// ✅ 정렬됨 - 이진 탐색 가능
const sorted = [1, 2, 5, 8, 9];
binarySearch(sorted, 8);  // 올바른 결과: 인덱스 3

어떻게 동작하나요?

책 페이지 찾기 비유

1000페이지 책에서 745페이지를 찾는다고 해보세요:

1단계: 중간(500페이지) 펼침
→ 745는 500보다 크니까 뒤쪽으로

2단계: 중간(750페이지) 펼침
→ 745는 750보다 작으니까 앞쪽으로

3단계: 중간(625페이지) 펼침
→ 745는 625보다 크니까 뒤쪽으로

... 계속 반으로 나누며 탐색 ...

10번 만에 찾음! (1000페이지를 직접 넘기면 745번 필요)

단계별 시각화

const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const target = 13;

// 1단계: 전체 범위
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
           ↑
        mid=9 (인덱스 4)
        13 > 9 → 오른쪽으로

// 2단계: 오른쪽 절반
[11, 13, 15, 17, 19]
     ↑
   mid=15 (인덱스 7)
   13 < 15 → 왼쪽으로

// 3단계: 좁혀진 범위
[11, 13]
     ↑
   mid=13 (인덱스 6)
   13 == 13 → 찾음! ✅

코드 구현

JavaScript 기본 구현

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;  // 못 찾음
}

// 사용 예시
const numbers = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(numbers, 7));   // 3
console.log(binarySearch(numbers, 10));  // -1 (없음)

TypeScript 제네릭 버전

function binarySearch<T>(
  arr: T[],
  target: T,
  compare: (a: T, b: T) => number = (a, b) => Number(a) - Number(b)
): number {
  let left = 0;
  let right = arr.length - 1;

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

    if (comparison === 0) {
      return mid;
    } else if (comparison < 0) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

// 객체 배열에서 사용
interface User {
  id: number;
  name: string;
}

const users: User[] = [
  { id: 1, name: 'Alice' },
  { id: 3, name: 'Bob' },
  { id: 5, name: 'Charlie' }
];

const index = binarySearch(
  users,
  { id: 3, name: '' } as User,
  (a, b) => a.id - b.id
);

console.log(users[index]);  // { id: 3, name: 'Bob' }

재귀 버전

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  // 기저 조건: 범위가 없으면 못 찾음
  if (left > right) {
    return -1;
  }

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) {
    return mid;
  }

  if (arr[mid] < target) {
    // 오른쪽 절반 재귀 탐색
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    // 왼쪽 절반 재귀 탐색
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

디버깅 버전

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

  console.log(`\n목표: ${target}`);
  console.log(`배열: [${arr}]\n`);

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

    console.log(`단계 ${step}:`);
    console.log(`  범위: [${left}, ${right}]`);
    console.log(`  중간: arr[${mid}] = ${arr[mid]}`);

    if (arr[mid] === target) {
      console.log(`  ✅ 찾음! 인덱스 ${mid}\n`);
      return mid;
    }

    if (arr[mid] < target) {
      console.log(`  ${arr[mid]} < ${target} → 오른쪽으로\n`);
      left = mid + 1;
    } else {
      console.log(`  ${arr[mid]} > ${target} → 왼쪽으로\n`);
      right = mid - 1;
    }

    step++;
  }

  console.log(`❌ 못 찾음\n`);
  return -1;
}

// 실행
binarySearchDebug([1, 3, 5, 7, 9, 11, 13, 15], 11);

출력:

목표: 11
배열: [1, 3, 5, 7, 9, 11, 13, 15]

단계 1:
  범위: [0, 7]
  중간: arr[3] = 7
  7 < 11 → 오른쪽으로

단계 2:
  범위: [4, 7]
  중간: arr[5] = 11
  ✅ 찾음! 인덱스 5

시간 복잡도: O(log n)

왜 O(log n)일까요?

매번 탐색 범위가 절반으로 줄어듭니다.

n = 1,000,000개
1회: 500,000개
2회: 250,000개
3회: 125,000개
...
20회: 1개

log₂(1,000,000) ≈ 20번

실제 비교

데이터 크기	선형 탐색	이진 탐색	차이
10	5번	3번	1.7배
100	50번	7번	7배
1,000	500번	10번	50배
1,000,000	500,000번	20번	25,000배

// 성능 비교
function compare(arr, target) {
  console.time('선형 탐색');
  arr.indexOf(target);
  console.timeEnd('선형 탐색');

  console.time('이진 탐색');
  binarySearch(arr, target);
  console.timeEnd('이진 탐색');
}

const big = Array.from({length: 1000000}, (_, i) => i);
compare(big, 999999);

// 선형 탐색: ~15ms
// 이진 탐색: ~0.001ms

변형: Lower Bound & Upper Bound

Lower Bound

target 이상인 첫 번째 원소의 인덱스

function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length;

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

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

const arr = [1, 2, 2, 2, 3, 5];
console.log(lowerBound(arr, 2));  // 1 (첫 번째 2의 인덱스)
console.log(lowerBound(arr, 4));  // 5 (4 이상인 첫 원소는 5)

Upper Bound

target보다 큰 첫 번째 원소의 인덱스

function upperBound(arr, target) {
  let left = 0;
  let right = arr.length;

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

    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

const arr = [1, 2, 2, 2, 3, 5];
console.log(upperBound(arr, 2));  // 4 (2보다 큰 첫 원소는 3)

실전 활용: 범위 찾기

// [start, end] 범위에 속하는 원소 개수
function countInRange(arr, start, end) {
  const lower = lowerBound(arr, start);
  const upper = upperBound(arr, end);
  return upper - lower;
}

const scores = [60, 70, 75, 80, 85, 90, 95];
console.log(countInRange(scores, 70, 90));  // 5개 (70~90점)

함정과 주의사항

함정 1: 정렬되지 않은 배열

// ❌ 잘못된 사용
const unsorted = [5, 2, 8, 1, 9];
binarySearch(unsorted, 8);  // 엉뚱한 결과!

// ✅ 올바른 사용
const sorted = [...unsorted].sort((a, b) => a - b);
binarySearch(sorted, 8);

함정 2: mid 계산 시 오버플로우

// ❌ 큰 배열에서 문제 발생 가능
const mid = (left + right) / 2;  // left + right가 너무 크면?

// ✅ 안전한 방법
const mid = Math.floor(left + (right - left) / 2);

// 또는 (JavaScript는 큰 수도 괜찮음)
const mid = Math.floor((left + right) / 2);

함정 3: <= vs <

// 이것이 가장 헷갈리는 부분!

// ❌ 무한 루프 가능
while (left < right) {  // right가 length일 때 문제
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  // ...
}

// ✅ 일반적으로 안전
while (left <= right) {
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) {
    left = mid + 1;  // mid는 제외
  } else {
    right = mid - 1;  // mid는 제외
  }
}

실전 활용 예시

1. 자동완성

// 단어 사전에서 접두사로 시작하는 단어 찾기
function autocomplete(dictionary, prefix) {
  const start = lowerBound(dictionary, prefix);

  const results = [];
  for (let i = start; i < dictionary.length; i++) {
    if (!dictionary[i].startsWith(prefix)) break;
    results.push(dictionary[i]);
  }

  return results;
}

const words = ['apple', 'application', 'apply', 'banana', 'band'];
console.log(autocomplete(words, 'app'));
// ['apple', 'application', 'apply']

2. 최적값 찾기

// "최소 몇 시간을 공부해야 90점 이상을 받을까?"
function minimumHours(scores, targetScore) {
  // scores[i] = i시간 공부했을 때의 예상 점수
  // scores는 오름차순 정렬되어 있음

  const index = lowerBound(scores, targetScore);
  return index < scores.length ? index : -1;
}

const studyScores = [60, 70, 75, 80, 85, 90, 92, 95];
console.log(minimumHours(studyScores, 90));  // 5시간

3. 중복 원소 개수

function countOccurrences(arr, target) {
  const lower = lowerBound(arr, target);
  const upper = upperBound(arr, target);
  return upper - lower;
}

const numbers = [1, 2, 2, 2, 3, 3, 5];
console.log(countOccurrences(numbers, 2));  // 3개
console.log(countOccurrences(numbers, 4));  // 0개

연습 문제

1. 기본 구현

// 이진 탐색을 직접 구현해보세요
function binarySearch(arr, target) {
  // 여기에 코드 작성
}

const arr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(arr, 7));   // 3
console.log(binarySearch(arr, 10));  // -1

2. 첫 등장 위치

// target이 처음 등장하는 인덱스 찾기
function findFirst(arr, target) {
  // 힌트: Lower Bound 활용
}

const arr = [1, 2, 2, 2, 3, 5];
console.log(findFirst(arr, 2));  // 1

3. 회전된 배열에서 최소값

// 회전된 정렬 배열에서 최소값 찾기
// [4, 5, 6, 7, 0, 1, 2] → 0

function findMin(arr) {
  // 힌트: 이진 탐색 응용
}

참고 자료

공식 문서 및 표준

ECMAScript® 2023 - Array.prototype.indexOf - 선형 탐색의 표준 구현
MDN Web Docs - Array Methods - 배열 메서드 전체 문서
C++ std::binary_search - 표준 라이브러리 구현

학술 자료 및 이론

Binary Search - Wikipedia - 역사와 수학적 분석
Introduction to Algorithms (CLRS) - Chapter 2.3 Designing Algorithms
Binary Search Analysis (PDF) - CMU 강의 자료
The Art of Computer Programming, Vol. 3 - Donald Knuth, Searching and Sorting

시각화 및 학습 도구

VisuAlgo - Binary Search - 인터랙티브 시각화
Algorithm Visualizer - Binary Search - 단계별 실행
Khan Academy - Binary Search - 개념 설명

실습 문제

LeetCode - Binary Search - 100+ 연습 문제
HackerRank - Search - 탐색 알고리즘 문제

심화 주제

Lower Bound / Upper Bound - C++ STL 문서
Interpolation Search - 이진 탐색의 개선
Exponential Search - 무한 배열에서의 탐색

마치며

이진 탐색은 “정렬된 데이터”라는 전제만 있으면 엄청난 성능을 제공합니다.

처음에는 left, right, mid의 관계가 헷갈릴 수 있지만, 10번 정도 직접 구현해보면 자연스러워집니다.

핵심은 “절반씩 줄여나간다”는 것입니다! 🎯

다음 단계

같은 레벨 (초중급):

삽입 정렬 - 비슷한 난이도
재귀 개념 - 이진 탐색을 재귀로 이해하기

다음 레벨 (중급):

이진 탐색 트리 - 이진 탐색의 자료구조 버전
퀵 정렬 - 이진 탐색의 분할 정복 원리 활용
DFS/BFS - 트리/그래프 탐색으로 확장

실전 응용:

다익스트라 - 우선순위 큐 + 이진 탐색 원리
동적 프로그래밍 - 최적화 문제에서의 활용

🚀 추천 학습 순서: 버블 정렬 → 이진 탐색 → 재귀 → DFS/BFS → 동적 프로그래밍