[Java] 알고리즘 - 이분탐색(Binary Search)

이지연·2026년 1월 3일

백엔드(Java, 알고리즘, spring)

목록 보기

44/89

개요

아래 내용은 이분탐색(Binary Search) 알고리즘의 핵심 개념을 먼저 정리한 뒤, A7이분탐색 패키지의 실습 코드(A01BinarySearch.java)를 통해 “문제 정의 → 탐색 아이디어 → 반복 구조 → 복잡도 분석 → 응용”의 흐름으로 정리한 글이다.

A01BinarySearch.java

이분탐색(Binary Search)이란?

이분탐색(이진검색)은 정렬된 배열에서 특정 값을 탐색할 때 사용하는 대표적인 효율적 알고리즘이다.
탐색 범위를 절반씩 줄여가므로 시간복잡도는 O(log n) 수준으로 매우 빠르다.

연속된 데이터에서 “어느 위치에 값이 존재하는지”를 찾아야 할 때, 전체를 살펴보는 대신 반을 날려가며 확인하는 방식이다.

작동 원리

탐색 범위 설정:
- 시작 인덱스 start, 끝 인덱스 end로 범위를 잡는다.
중간점(mid) 계산:
- mid = (start + end) / 2
중간값 비교:
- arr[mid] == target → 찾았다! 리턴
- arr[mid] > target → 오른쪽은 탈락, end = mid - 1
- arr[mid] < target → 왼쪽은 탈락, start = mid + 1
반복 종료 조건:
- start > end가 되면 탐색 실패

이 과정을 통해 탐색 구간이 절반씩 줄어들기 때문에 log₂(n) 단계 만에 결과를 찾는다.

실습 1: 기본 이분탐색

arr = {1,3,5,7,9,11,13,15,17,19}
target = 17

구현 흐름

정렬 전제: 이미 정렬된 배열에서만 가능
인덱스 초기화: start=0, end=arr.length-1
while문으로 탐색 반복
조건에 따라 start/end 옮기기

코드 요약

int startIdx = 0;
int endIdx = arr.length - 1;
int targetIdx = -1;

while (startIdx <= endIdx) {
    int mid = (startIdx + endIdx) / 2;

    if (arr[mid] > target) {
        endIdx = mid - 1;
    } else if (arr[mid] < target) {
        startIdx = mid + 1;
    } else {
        targetIdx = mid;
        break;
    }
}

System.out.println(targetIdx); // 결과: 8

복잡도

시간복잡도: O(log n)
공간복잡도: O(1)

완전탐색이 n번 비교했다면, 이분탐색은 log₂(10) ≈ 3~4번 만에 값(17)을 찾아낸다.

실습 2: 존재하지 않는 값 처리 (응용 문제)

때로는 target이 배열에 없을 수도 있다.
이 경우 “값이 들어가야 할 위치(index)”를 반환하도록 응용할 수 있다.

int target2 = 4;
int startIdx2 = 0, endIdx2 = arr.length - 1;
int targetIdx2 = -1;

while (startIdx2 <= endIdx2){
    int mid = (startIdx2 + endIdx2) / 2;

    if (arr[mid] > target2) {
        endIdx2 = mid - 1;
        targetIdx2 = mid; // mid 위치가 삽입될 자리 후보
    } else if (arr[mid] < target2) {
        startIdx2 = mid + 1;
    } else {
        targetIdx2 = mid;
        break;
    }
}

System.out.println(targetIdx2);  // 결과: 2 → 4가 들어가야 할 자리 예상

이렇게 하면 없을 경우 삽입 위치를 리턴하는 변형된 이분탐색(upper/lower bound)으로도 활용 가능하다.
자바 Arrays.binarySearch()도 이 원리를 내부적으로 사용한다.

응용 분야

이분탐색은 단순히 “정확히 일치하는 값 찾기”를 넘어서 다음과 같이 다양한 문제로 발전한다.

범위 내 조건 만족하는 최댓값/최솟값 찾기 → upper bound / lower bound 개념
정렬 조건이 유지되는 배열 내에서 특정 경계값 찾기
결정 문제(Optimization + Parametric Search)
- 예: “어떤 값 mid 이하로 제한했을 때 조건을 만족하는가?”

예를 들어 ‘나무 자르기’, ‘입국 심사’, ‘징검다리’ 같은 문제들은
모두 이분탐색 원리를 확장해 탐색 구간(숫자)을 조절하는 형태로 해결된다.