[알고리즘] 이분 탐색과 매개변수 탐색의 개념과 이해

이 글인 이분 탐색(Binary Search)과 매개변수 탐색(Parametric Search)에 대해 정리한 글입니다.

---

📚 이분 탐색 (Binary Search)

📖 이분 탐색의 개념

➡️ 이분 탐색(Binary Search)은 정렬된(오름차순 or 내림차순) 자료구조에서 원하는 값을 빠르게 찾는 알고리즘

⚡ 기본 아이디어

• 탐색 범위를 절반씩 줄여가면서 원하는 값을 찾는다.
• 매 단계마다 "중간" 지점을 확인하고, 이 중간값을 기준으로 범위를 왼쪽 / 오른쪽 반으로 나눈다.

⚡ 필수 조건

• 반드시 배열(또는 리스트)이 정렬되어 있어야 한다.
  • 오름차순, 내림차순 둘 다 가능 (단, 비교 방식은 달라진다.)
  • 정렬되지 않은 상태에서 이분 탐색을 수행하면 올바른 결과를 얻을 수 없음

---

📖 이분 탐색의 원리 (동작 과정)

출처: https://commons.wikimedia.org/wiki/File:Binary_Search_Example.png

• 탐색 범위 설정
  • 시작점(start or left or lo)과 끝점 (end or right or hi) 설정
  • 일반적으로 start = 0, end = N - 1로 설정
• 반복 탐색 수행 (while문)
  • start <= end가 성립할 때 반복
• 중간 인덱스 계산 (mid)
  • mid = (start + end) / 2
  • 오버플로우 방지를 위해 mid = start + (end - start) / 2로 사용하기도 함
• 값 비교
  • arr[mid] == target : 값 찾음
  • arr[mid] < target : 타겟 값이 오른쪽에 존재 ➡️ start = mid + 1
  • arr[mid] > target : 타겟 값이 왼쪽에 존재 ➡️ end = mid - 1
• 탐색 종료
  • 값을 찾으면 반환
  • 찾지 못하면 -1 (혹은 실패했을 때의 값) 반환

---

📖 이분 탐색의 시간 복잡도

• $ O(\log N) $ : 한번 탐색 마다 탐색 구간이 절반이 됨

⚡ 이분 탐색의 장점

• 매우 빠르다. (순차 탐색 $ O(N) $ vs 이분 탐색 $ O(\log N) $)
• 대용량 데이터에서 성능이 압도적이다.

⚡ 이분 탐색의 한계점

• 반드시 정렬이 되어 있어야 한다.
• 배열이 아닌 일반적인 연결리스트에는 부적합하다. (임의 접근이 느림)
• 탐색 대상의 구조에 따라 구현 방식이 달라질 수 있다.

---

📖 이분 탐색 코드 예시

⚡ C++

int binary_search(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(arr[mid] == target) return mid;
        else if(arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

⚡ C

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid; // 찾은 경우 인덱스 반환
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1; // 찾지 못한 경우
}

⚡ Java

import java.util.*;

public class Main {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target)
                return mid; // 찾은 경우 인덱스 반환
            else if (arr[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1; // 찾지 못한 경우
    }

    public static void main(String[] args) {
        ...
    }
}

---

📖 이분 탐색의 응용

⚡ Lower Bound / Upper Bound

vector<int> arr = {2, 4, 4, 4, 5, 7};
int idx1 = lower_bound(arr.begin(), arr.end(), 4) - arr.begin(); // 1
int idx2 = upper_bound(arr.begin(), arr.end(), 4) - arr.begin(); // 4

• Lower Bound
  • target 이상이 처음 등장하는 위치 (인덱스)
  • C++ STL : lower_bound
• Upper Bound
  • target을 초과하는 값이 처음 등장하는 위치
  • C++ STL : upper_bound

⚡ 변형된 이분 탐색

• 단순한 값 탐색을 넘어서, 최적의 값(최소 / 최대, 조건 만족 경계 등)을 찾는데 자주 사용됨

➡️ 매개변수 탐색(Parametric Search)의 기초가 됨

---

📚 매개변수 탐색 (Parametric Search)

📖 매개변수 탐색의 개념

➡️ 매개변수 탐색(Parametric Search)은 "어떤 값(매개변수)이 특정 조건을 만족하는가?"를 결정하는 문제에서 이분 탐색을 이용해 "최적의 값"을 찾는 알고리즘

⚡ 핵심 아이디어

• 단순히 값의 존재 유무를 찾는 것이 아니라 조건을 만족하는 최댓값, 최솟값, 혹은 경계값을 찾는데 사용
• 답이 값 그 자체가 아니라, "조건을 만족하는 범위 내 최적 값"이 되는 구조

---

📖 일반적인 이분 탐색과의 차이점

➡️ 일반 이분 탐색은 값(인덱스, 존재 여부)을 직접 찾고, 매개변수 탐색은 "정답의 후보가 될 수 있는 수 전체"에서 최적 경계값을 찾는데 사용

구분	일반 이분 탐색	매개변수 탐색
목적	배열에 ‘특정 값’이 있는지 탐색	조건을 만족하는 ‘최적의 값’을 찾기
탐색 대상	배열의 원소	정답의 후보가 될 수 있는 “범위(숫자)”
비교 기준	arr[mid] == target	check(mid) == true/false
종료 후 답	값이 존재하면 그 위치(값)	탐색 과정에서 경계/최대/최소 값 추적

---

📖 매개변수 탐색의 흐름

• 정답이 될 수 있는 구간(범위)을 정한다.
• mid(중간값)를 정해서, 이 값이 조건을 만족하는지 체크한다.
  • 보통 check(mid) 함수로 구현
• check(mid) 결과에 따라 탐색 구간을 좁힌다.
  • true : 최소/최대 조건에 따라 lo/hi를 mid ± 1로 갱신
  • false : 반대 방향으로 구간을 조정
• 탐색이 끝나면, 원하는 최적값(최소 / 최대 / 경계값 등)을 출력

---

📖 매개변수 탐색의 대표 패턴

⚡ 최대화 / 최소화 문제

• 최대값(혹은 최소값) 중 조건을 만족하는 값 찾기

⚡ Lower Bound / Upper Bound

• lower_bound : 조건을 만족하는 최소값
• upper_bound : 조건을 만족하지 않는 첫 값 (또는 조건을 만족하는 최대값 + 1)

---

📖 매개변수 탐색의 구현 패턴

lo = 최소 가능값
hi = 최대 가능값
answer = 0 (혹은 큰 값, 작은 값)

while (lo <= hi) {
    mid = (lo + hi) / 2
    if (check(mid)) {
        answer = mid // 또는 answer = min(answer, mid), max(answer, mid)
        lo = mid + 1 // 또는 hi = mid - 1 (문제에 따라)
    } else {
        hi = mid - 1 // 또는 lo = mid + 1 (문제에 따라)
    }
}
출력 answer

• check 함수 시간복잡도 : $ O(N) $
• 전체 시간 복잡도 : $ O(\log maxV) * O(N) $

⚡ Cpp

int left = 1, right = *max_element(arr.begin(), arr.end());
int answer = 0;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}
cout << answer;

⚡ C

int lo = 1, hi = 1e9, answer = 0;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (check(mid)) {
        answer = mid;
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}
printf("%d\n", answer);

⚡ Java

int lo = 1, hi = 1000000000, answer = 0;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (check(mid)) {
        answer = mid;
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}
System.out.println(answer);

---