이분 탐색 (Binary Search)

이분 탐색은 정렬된 배열에서 특정 값을 찾거나 범위를 구할 때 사용되는 효율적인 알고리즘. 이분 탐색은 배열을 반으로 나누면서 탐색 범위를 좁혀 나가며 원하는 값을 찾는다.

기본 이분 탐색 원리

이분 탐색은 다음과 같은 단계로 이루어집니다:
1. 배열의 중간 값을 찾는다.
2. 중간 값이 찾고자 하는 값과 같으면 탐색을 종료.
3. 중간 값이 찾고자 하는 값보다 크면 중간 값의 왼쪽 부분 배열에서 탐색
4. 중간 값이 찾고자 하는 값보다 작으면 중간 값의 오른쪽 부분 배열에서 탐색
5. 찾고자 하는 값을 찾거나 탐색 범위가 없을 때까지 이 과정을 반복

이분 탐색의 시간 복잡도

이분 탐색의 시간 복잡도는 O(log n)
절반씩 줄여나간다고 생각하면 된다.

• 상한 (Upper Bound) 찾기

  상한은 주어진 값보다 큰 첫 번째 요소의 위치를 찾는 과정.
  1. 배열의 중간 값을 찾는다.
  2. 중간 값이 주어진 값보다 작거나 같으면 중간 값의 오른쪽 부분 배열에서 탐색
  3. 중간 값이 주어진 값보다 크면 중간 값의 위치를 기록하고 왼쪽 부분 배열에서 탐색
  4. 배열의 끝에 도달하거나 주어진 값보다 큰 값을 찾을 때까지 반복
  

public int upperBound(int[] array, int target) {
    int left = 0;
    int right = array.length;

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

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

    return left;
}

• 하한 (Lower Bound) 찾기

  하한은 주어진 값 이상중 첫 번째 요소의 위치를 찾는 과정.
  1. 배열의 중간 값을 찾는다.
  2. 중간 값이 주어진 값보다 작으면 중간 값의 오른쪽 부분 배열에서 탐색
  3. 중간 값이 주어진 값보다 크거나 같으면 중간 값의 위치를 기록하고 왼쪽 부분 배열에서 탐색
  4. 배열의 끝에 도달하거나 주어진 값보다 작지 않은 값을 찾을 때까지 이 과정을 반복

public int lowerBound(int[] array, int target) {
    int left = 0;
    int right = array.length;

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

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

    return left;
}

---

파라매트릭 서치(Parametric Search)

매우 중요

최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제(decision problem)로 바꾸어 푸는 것

1. 문제 예시

   여러 개의 짐을 싣고 있는 배가 있다. 각 짐의 무게가 주어졌을 때, 배가 견딜 수 있는 최대 무게를 넘지 않으면서 배에 최대한 많은 짐을 싣고 싶다. 배의 최대 무게가 maxWeight로 주어졌을 때, 배에 실을 수 있는 최대 짐의 무게를 구시오.

public class ParametricSearch {
    // 주어진 무게로 배에 짐을 실을 수 있는지 확인하는 함수
    public static boolean canLoad(int[] weights, int maxWeight, int limit) {
        int currentWeight = 0;
        for (int weight : weights) {
            if (currentWeight + weight > limit) {
                return false;
            }
            currentWeight += weight;
        }
        return currentWeight <= maxWeight;
    }

    // 파라메트릭 서치 함수
    public static int parametricSearch(int[] weights, int maxWeight) {
        int left = 0;
        int right = maxWeight;
        int result = 0;

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

            if (canLoad(weights, maxWeight, mid)) {
                result = mid; // 가능한 최대 무게 갱신
                left = mid + 1; // 더 큰 무게를 탐색
            } else {
                right = mid - 1; // 더 작은 무게를 탐색
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30, 40, 50};
        int maxWeight = 100;
        System.out.println("배에 실을 수 있는 최대 무게: " + parametricSearch(weights, maxWeight));
    }
}