이진 탐색 (binary search)

 

그래프 탐색 알고리즘이 아닌 배열 기반 탐색에서 가장 자주 등장하는 알고리즘이 바로 이진 탐색(Binary Search)이다.
이진 탐색은 정렬된 데이터를 전제로 하여, 탐색 범위를 절반씩 줄여가며 원하는 값을 찾아내는 매우 효율적인 알고리즘이다.

구현과 원리가 비교적 단순하지만, 시간 복잡도가 뛰어나기 때문에 코딩 테스트에서는 단독 문제뿐만 아니라 부분 문제로도 자주 활용된다.

이번 글에서는 이진 탐색의 개념과 특징, 동작 원리, 시간 복잡도를 중심으로 정리해보려고 한다. ✍️

 

 

---

 

 

이진 탐색이란?

이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 빠르게 찾아내는 탐색 알고리즘이다.

탐색 대상의 중앙값과 찾고자 하는 값을 비교하면서,
조건에 따라 탐색 범위를 절반씩 줄여 나가는 방식으로 동작한다.

 

즉,

• 전체 데이터의 중앙값을 기준으로 비교하고
• 타깃 값이 더 작으면 왼쪽 범위를 선택하고
• 타깃 값이 더 크면 오른쪽 범위를 선택하며
• 탐색 범위를 점점 좁혀간다

이러한 방식 때문에 이진 탐색은 탐색 속도가 매우 빠른 알고리즘이다. 🔍

 

 

---

 

 

이진 탐색의 특징 🔧

이진 탐색의 핵심 특징은 다음과 같다.

• 정렬된 데이터에서만 사용 가능
• 중앙값 비교를 통한 탐색 범위 축소 방식
• 탐색할 때마다 데이터의 크기가 절반으로 감소
• 구현 방식이 단순하여 반복문 또는 재귀로 구현 가능

특히 “정렬되어 있다”는 조건이 매우 중요하다.
정렬되지 않은 데이터에서는 이진 탐색을 사용할 수 없다는 점을 반드시 기억해야 한다. ⚠️

이진 탐색은 원하는 값을 빠르게 찾는 ‘검색(Search)’ 기능에 특화된 알고리즘이다.

 

 

---

 

 

이진 탐색의 동작 원리 🔁

이진 탐색은 오름차순으로 정렬된 데이터를 기준으로 다음 과정을 반복한다.
(내림차순이라면 비교 조건만 반대로 적용하면 된다.)

 

1. 현재 데이터셋의 중앙값을 선택한다.
2. 중앙값 > 타깃 데이터인 경우, 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터인 경우, 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 위 과정을 반복하다가 중앙값이 타깃 데이터와 같아지면 탐색을 종료한다.

이 과정을 통해 탐색 범위는 매 단계마다 절반씩 줄어든다.

타깃 데이터가 31인 경우 과정

 

 

---

 

 

시간 복잡도 ⏰

이진 탐색의 시간 복잡도는 다음과 같다.

O(log N)

• 탐색할 때마다 데이터의 크기가 절반으로 줄어들기 때문이다.

선형 탐색(O(N))과 비교하면, 데이터의 크기가 커질수록 이진 탐색의 효율성은 압도적으로 커진다.

이 때문에 이진 탐색은 대용량 데이터 처리와 빠른 검색이 필요한 상황에서 매우 강력하다.

 

 

---

 

 

이진 탐색이 자주 사용되는 문제들

이진 탐색은 단순한 값 찾기뿐만 아니라,
조건을 만족하는 최소·최대 값을 찾는 문제에서도 자주 활용된다.

• 정렬된 배열에서 특정 값 찾기
• 특정 조건을 만족하는 최소/최대 값 찾기
• 파라메트릭 서치(Parametric Search)
• 결정 문제(YES / NO 판단 문제)

이진 탐색의 개념을 잘 이해해두면 문제를 보고 “이건 이진 탐색으로 풀 수 있겠다”는 감각이 자연스럽게 생긴다.

 

+ 아래 문제들을 풀어 보시면 좋습니다!

https://www.acmicpc.net/workbook/view/1065