한국어
메뉴

이진 탐색(Binary Search)란?

정렬된 데이터에서 가운데 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 탐색 방법. n개의 데이터에서 최대 ⌊log₂ n⌋ + 1회의 비교로 찾을 수 있으며, 시간 복잡도는 O(log n). 데이터가 정렬되어 있는 것이 전제가 된다.

일본어 명칭: 二分探索

이진 탐색(Binary Search)은(는) 자료 구조와 알고리즘, A/D·D/A 변환, 소프트웨어 개발과 프로젝트 관리 등 3개 분야의 연습 문제 7개에 나와요.

분야: 자료 구조와 알고리즘

도전해 보기: 이진 탐색(Binary Search) 관련 문제

배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?

  1. A데이터의 개수가 2의 거듭제곱일 것
  2. B데이터가 키 순서로 정렬되어 있을 것
  3. C데이터에 같은 값이 포함되어 있지 않을 것
정답과 해설 보기

정답: B. 데이터가 키 순서로 정렬되어 있을 것

이진 탐색은 가운데 원소와 비교한 결과로 목표 값이 앞쪽 절반과 뒤쪽 절반 중 어디에 있는지를 정하여 범위를 절반으로 줄입니다. 이는 데이터가 정렬되어 있기 때문에 할 수 있는 판단이며, 정렬되어 있지 않은 배열에는 사용할 수 없습니다. 데이터의 개수가 2의 거듭제곱이 아니어도, 가운데 위치를 (하한 + 상한) ÷ 2의 버림 등으로 정하면 문제없이 동작합니다. 같은 값이 포함되어 있어도 탐색은 가능하며, 그 값 중 어느 하나가 발견됩니다(첫 위치를 구하려면 약간의 궁리가 필요합니다).

오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?

  1. A10회
  2. B32회
  3. C500회
정답과 해설 보기

정답: A. 10회

1회의 비교로 찾는 범위가 거의 절반이 되며, 2¹⁰ = 1024 ≥ 1000이므로 최대 10회면 범위가 없어집니다(⌊log₂ 1000⌋ + 1 = 10). 시간 복잡도는 O(log n)이며, 100만 개라도 최대 20회면 됩니다. 32회는 √1000 ≈ 31.6에 해당하는 값이고, 500회는 선형 탐색의 평균(약 n/2)에 가까운 값입니다. 다만 이진 탐색을 사용하려면 데이터가 정렬되어 있어야 하며, 정렬에 드는 O(n log n)의 수고도 고려해야 합니다.

해설 속 이진 탐색(Binary Search)

이진 탐색(Binary Search)이(가) 나오는 문제 (7)

  1. 배열 가운데의 원소와 비교하여 찾는 범위를 절반씩 좁혀 가는 이진 탐색을 사용하기 위한 전제 조건으로 올바른 것은?
  2. 오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?
  3. 오름차순으로 늘어선 배열 a[0]~a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60에서 이진 탐색으로 38을 찾는다. 찾는 범위를 하한 lo = 0, 상한 hi = 9에서 시작하고, 가운데 위치를 (lo + hi) ÷ 2의 버림으로 한다. 38과 비교되는 원소의 값을 차례로 나열한 것은?
  4. 올바르게 동작하는 것으로 알려진 펌웨어 버전 뒤에 1,000개의 커밋이 있고, 최신 커밋에서는 결함이 일어난다. 결함은 어느 한 커밋에서 들어왔고, 그 이후의 커밋에서는 모두 일어난다고 한다. git bisect처럼 이진 탐색으로 원인 커밋을 특정할 때, 빌드하여 테스트하는 횟수의 최댓값은?
  5. 축차 비교형(SAR형) ADC의 동작으로 옳은 것은 무엇인가?
  6. N비트 축차 비교형 ADC가 1회 변환에서 수행하는 비교 횟수로 기본적으로 옳은 것은 무엇인가?
  7. 서로 다른 100개의 값이 들어 있는 배열에서, 앞에서부터 차례로 하나씩 비교하는 선형 탐색으로 목표 값을 찾는다. 목표 값은 반드시 배열 안에 있고 어느 위치에 있을 확률도 같을 때, 비교 횟수의 평균은 얼마인가?

관련 용어

배열(Array) 시간 복잡도(Time Complexity) Git 비교기(comparator) 마이컴(마이크로컨트롤러) 오버샘플링(Oversampling) 축차 비교형 ADC(SAR ADC) 깊이 우선 탐색(Depth-First Search) 너비 우선 탐색(Breadth-First Search) 다익스트라 알고리즘(Dijkstra's Algorithm)

용어집으로 돌아가기