이분 탐색(Binary Search), 정렬된 데이터에서 절반씩 줄여 찾기

이분 탐색

이분 탐색은 영어로 Binary Search라고 한다.
처음에는 이름이 조금 어렵게 느껴졌는데, 개념 자체는 생각보다 단순하다.

핵심은 이것이다.

정렬된 데이터에서 가운데 값을 확인하고,
필요 없는 절반을 버리면서 원하는 값을 찾는 방법이다.

즉, 처음부터 끝까지 하나씩 확인하는 것이 아니라,
범위를 계속 절반으로 줄여가며 찾는 탐색 방법이다.

---

이분 탐색이란?

이분 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘이다.

예를 들어 1부터 100까지 숫자 중에서 73을 찾는다고 해보자.

하나씩 찾는다면 이렇게 확인해야 한다.

1, 2, 3, 4, 5, ... 73

운이 나쁘면 꽤 많은 숫자를 확인해야 한다.

하지만 이분 탐색은 가운데부터 본다.

1 ~ 100의 가운데쯤인 50을 확인한다.
73은 50보다 크다.
그러면 1 ~ 50은 볼 필요가 없다.

이제 범위는 51 ~ 100으로 줄어든다.

다시 가운데를 확인한다.

51 ~ 100의 가운데쯤인 75를 확인한다.
73은 75보다 작다.
그러면 76 ~ 100은 볼 필요가 없다.

이런 식으로 계속 범위를 절반씩 줄여가며 원하는 값을 찾는다.

---

이분 탐색의 핵심 조건

이분 탐색에서 가장 중요한 조건은 데이터가 정렬되어 있어야 한다는 것이다.

예를 들어 아래 배열은 이분 탐색이 가능하다.

int[] arr = {1, 3, 5, 7, 9, 11};

오름차순으로 정렬되어 있기 때문이다.

하지만 아래 배열은 바로 이분 탐색을 하기 어렵다.

int[] arr = {7, 1, 11, 3, 9, 5};

정렬되어 있지 않으면 가운데 값을 보고 왼쪽으로 갈지, 오른쪽으로 갈지 판단할 수 없다.

이분 탐색은 가운데 값을 기준으로 이렇게 판단한다.

target이 mid 값보다 크다  → 오른쪽 탐색
target이 mid 값보다 작다 → 왼쪽 탐색

이 판단이 가능하려면 배열이 정렬되어 있어야 한다.

그래서 이분 탐색을 하기 전에는 보통 정렬을 먼저 한다.

Arrays.sort(arr);

---

순차 탐색과 이분 탐색 비교

이분 탐색을 이해하려면 순차 탐색과 비교해보면 쉽다.

구분순차 탐색이분 탐색

탐색 방식	앞에서부터 하나씩 확인	가운데부터 확인
조건	정렬 필요 없음	정렬 필요
범위 줄이기	한 칸씩 이동	절반씩 줄임
시간복잡도	O(N)	O(log N)

순차 탐색은 단순하지만 데이터가 많아지면 오래 걸릴 수 있다.
반면 이분 탐색은 정렬되어 있다는 조건만 만족하면 훨씬 빠르게 찾을 수 있다.

---

이분 탐색에서 사용하는 변수

이분 탐색에서는 보통 세 가지 변수를 사용한다.

변수의미

left	현재 탐색 범위의 시작 인덱스
right	현재 탐색 범위의 끝 인덱스
mid	현재 탐색 범위의 가운데 인덱스

예를 들어 배열이 다음과 같다고 하자.

int[] arr = {1, 3, 5, 7, 9, 11};

처음에는 배열 전체를 탐색 범위로 잡는다.

int left = 0;
int right = arr.length - 1;

가운데 인덱스는 이렇게 구한다.

int mid = left + (right - left) / 2;

처음에는 아래처럼 생각하기 쉬웠다.

int mid = (left + right) / 2;

작은 숫자에서는 두 코드의 결과가 같다.
하지만 left와 right가 아주 큰 경우에는 left + right가 int 범위를 넘어 오버플로우가 날 수 있다.

그래서 더 안전하게 쓰려면 아래 방식을 사용하는 것이 좋다.

int mid = left + (right - left) / 2;

이 방식은 left와 right를 먼저 더하지 않고,
right - left로 거리의 절반을 구한 뒤 left에 더하는 방식이다.

즉, 같은 가운데 값을 구하지만 더 안전한 표현이다.

---

이분 탐색 흐름

찾고 싶은 값이 9라고 해보자.

int[] arr = {1, 3, 5, 7, 9, 11};
int target = 9;

처음 범위는 전체 배열이다.

left = 0
right = 5

가운데를 구하면:

mid = 2
arr[mid] = 5

target인 9는 5보다 크다.
그러면 5보다 왼쪽에 있는 값들은 볼 필요가 없다.

그래서 left를 이동시킨다.

left = mid + 1;

이제 탐색 범위는 오른쪽으로 줄어든다.

left = 3
right = 5

다시 가운데를 구한다.

mid = 4
arr[mid] = 9

target과 같으므로 값을 찾은 것이다.

---

Java 코드로 작성하기

이분 탐색 기본 코드는 다음과 같다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 9;

        int left = 0;
        int right = arr.length - 1;

        boolean found = false;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

        System.out.println(found);
    }
}

---

코드 해석

1. 가운데 값을 확인한다

int mid = left + (right - left) / 2;

현재 탐색 범위에서 가운데 인덱스를 구한다.

---

2. 값을 찾은 경우

if (arr[mid] == target) {
    found = true;
    break;
}

가운데 값이 찾는 값과 같으면 탐색을 종료한다.

---

3. target이 더 큰 경우

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

가운데 값보다 target이 크다면 오른쪽에 있을 가능성이 있다.
그래서 왼쪽 범위는 버리고 left를 이동시킨다.

---

4. target이 더 작은 경우

else {
    right = mid - 1;
}

가운데 값보다 target이 작다면 왼쪽에 있을 가능성이 있다.
그래서 오른쪽 범위는 버리고 right를 이동시킨다.

---

왜 left <= right를 사용할까?

이분 탐색의 반복문은 보통 이렇게 작성한다.

while (left <= right)

처음에는 left < right와 헷갈릴 수 있다.

left와 right가 같은 경우는 탐색할 값이 딱 하나 남은 상태이다.
그 하나도 확인해야 하므로 left <= right를 사용한다.

예를 들어:

left = 3
right = 3

이면 아직 3번 인덱스 값을 확인해야 한다.

그래서 이분 탐색 기본 형태에서는 left <= right를 많이 사용한다.

---

범위 갱신에서 mid + 1, mid - 1을 쓰는 이유

가운데 값 arr[mid]는 이미 확인한 값이다.

그래서 다음 탐색 범위에서는 다시 볼 필요가 없다.

target이 더 크다면:

left = mid + 1;

target이 더 작다면:

right = mid - 1;

처럼 가운데 인덱스를 제외하고 범위를 줄인다.

만약 아래처럼 작성하면 문제가 생길 수 있다.

left = mid;
right = mid;

이렇게 하면 같은 mid를 계속 확인하게 되어 무한 반복이 생길 수 있다.

---

시간복잡도

이분 탐색은 한 번 확인할 때마다 탐색 범위가 절반으로 줄어든다.

예를 들어 데이터가 100개라면 이런 식으로 줄어든다.

100개
→ 50개
→ 25개
→ 12개
→ 6개
→ 3개
→ 1개

그래서 시간복잡도는 다음과 같다.

O(log N)

순차 탐색이 O(N)인 것과 비교하면 훨씬 빠르다.

탐색 방법시간복잡도

순차 탐색	O(N)
이분 탐색	O(log N)

데이터가 많아질수록 이 차이는 더 커진다.

---

공간복잡도

반복문으로 이분 탐색을 구현하면 추가로 큰 배열을 만들지 않는다.

left, right, mid 같은 변수만 사용한다.

따라서 공간복잡도는 다음과 같다.

O(1)

---

이분 탐색에서 자주 하는 실수

1. 정렬하지 않고 이분 탐색하기

이분 탐색은 정렬된 데이터에서만 사용할 수 있다.

정렬이 되어 있지 않으면 가운데 값을 기준으로 왼쪽/오른쪽을 판단할 수 없다.

---

2. while 조건 실수

기본 이분 탐색에서는 보통 아래 조건을 사용한다.

while (left <= right)

값이 하나 남은 경우까지 확인해야 하기 때문이다.

---

3. 범위 갱신 실수

가운데 값은 이미 확인했으므로 다음 범위에서 제외해야 한다.

left = mid + 1;
right = mid - 1;

이 부분을 잘못 쓰면 무한 반복이 생길 수 있다.

---

4. mid 계산 오버플로우

아래 방식은 작은 숫자에서는 괜찮다.

int mid = (left + right) / 2;

하지만 left와 right가 매우 클 경우 left + right에서 오버플로우가 발생할 수 있다.

그래서 아래 방식을 습관화하면 좋다.

int mid = left + (right - left) / 2;

---

이분 탐색은 언제 떠올리면 좋을까?

문제에서 이런 느낌이 나오면 이분 탐색을 의심해볼 수 있다.

정렬된 배열에서 특정 값을 찾는다.
탐색 범위가 매우 크다.
하나씩 확인하면 시간이 부족하다.
조건을 만족하는 최소값을 찾아야 한다.
조건을 만족하는 최대값을 찾아야 한다.

처음에는 단순히 배열에서 target을 찾는 문제부터 연습하면 좋다.
이후에는 “정답의 범위”를 두고 이분 탐색하는 문제로 넘어가면 된다.

예를 들어 이런 문제들이 있다.

특정 값이 배열에 있는지 찾기
조건을 만족하는 가장 작은 값 찾기
조건을 만족하는 가장 큰 값 찾기
공유기 설치
입국심사
예산
랜선 자르기

이런 문제들은 단순히 값이 배열 안에 있는지 찾는 것보다 조금 더 어렵다.
하지만 핵심은 같다.

가운데 값을 기준으로 가능/불가능을 판단하고,
필요 없는 절반을 버린다.

---

내가 이해한 이분 탐색 핵심

이번에 이분 탐색을 공부하면서 가장 중요하게 느낀 점은 이것이다.

이분 탐색은 정렬된 상태에서만 가능하다.

정렬되어 있어야 가운데 값을 기준으로 왼쪽을 버릴지, 오른쪽을 버릴지 판단할 수 있다.

그리고 실제 코드에서는 세 가지 변수를 잘 관리해야 한다.

left  = 탐색 범위의 시작
right = 탐색 범위의 끝
mid   = 탐색 범위의 가운데

탐색 흐름은 이렇게 정리할 수 있다.

1. 가운데 값을 확인한다.
2. target과 비교한다.
3. target이 더 크면 오른쪽만 본다.
4. target이 더 작으면 왼쪽만 본다.
5. 찾을 때까지 반복한다.

---

마무리

이분 탐색은 이름만 보면 어렵게 느껴지지만, 결국 핵심은 단순하다.

정렬된 데이터에서 가운데를 확인하고,
필요 없는 절반을 버리면서 찾는 방법이다.

하나씩 전부 확인하는 것보다 훨씬 빠르기 때문에,
데이터가 많고 정렬이 가능하거나 이미 정렬되어 있는 문제에서 자주 사용된다.

앞으로 이분 탐색 문제를 풀 때는 먼저 아래 질문을 해봐야겠다.

1. 데이터가 정렬되어 있는가?
2. 가운데 값을 기준으로 왼쪽/오른쪽을 버릴 수 있는가?
3. 하나씩 확인하면 시간이 너무 오래 걸리는가?
4. 조건을 만족하는 최소값 또는 최대값을 찾는 문제인가?

이 질문에 해당한다면 이분 탐색을 떠올려볼 수 있다.

특히 구현할 때는 아래 세 가지를 조심해야겠다.

while 조건은 left <= right
범위 갱신은 mid + 1, mid - 1
mid 계산은 left + (right - left) / 2

이분 탐색은 단순한 값 찾기부터 시작해서, 나중에는 정답의 범위를 줄여가는 문제까지 확장된다.
이번에는 기본 개념을 정리했으니, 다음에는 직접 문제를 풀면서 left, right, mid를 어떻게 잡는지 연습해봐야겠다.