이진 탐색 ( Binary Search )

이진 탐색

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 효율적으로 찾는 알고리즘이다. 변수 3개( start, end, mid )를 사용하여 탐색하며 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

기본 원리

• 배열 정렬: 이진 탐색을 수행하기 전에, 배열은 정렬되어 있어야 한다.
• 중앙 값 확인: 배열의 중앙에 위치한 값을 확인한다.
• 탐색 범위 조정:
  - 만약 중앙 값이 찾고자 하는 값보다 크면, 탐색 범위를 배열의 왼쪽 절반으로 줄인다.
  - 만약 중앙 값이 찾고자 하는 값보다 작으면, 탐색 범위를 배열의 오른쪽 절반으로 줄인다.
• 반복 또는 종료:
  - 찾고자 하는 값이 중앙 값과 같다면 탐색을 종료한다.
  - 찾고자 하는 값이 중앙 값이 아니면, 새로 조정된 탐색 범위에 대해 이진 탐색을 반복한다.

이진 탐색은 배열이 정렬되어 있다는 전제 하에, 선형 탐색보다 훨씬 빠르게 원하는 값을 찾을 수 있다. 시간 복잡도는 O(log n) 이다. 여기서 n 은 배열의 크기이다.

예제

이진 탐색을 활용할 수 있는 전형적인 문제는 "최적화 문제에서의 결정 문제 변환"이다.

문제: 프로젝트 예산 최적화

당신은 기업의 프로젝트 매니저이며, 여러 개의 프로젝트 중에서 예산 내에서 최대한 많은 프로젝트를 완료하고자 한다. 각 프로젝트는 다른 비용을 필요로 하며, 모든 프로젝트의 비용이 주어진다. 주어진 총 예산 내에서 최대 몇 개의 프로젝트를 완료할 수 있는지 결정해야 한다.

• 입력 :
  projects : 각 프로젝트의 비용을 담은 정수 배열
  budget : 사용할 수 있는 총 예산

• 출력 :
  최대 완료할 수 있는 프로젝트의 수

• 예시 :
  projects = {100, 200, 50, 80, 30}
  budget = 300
  출력: 4 (30, 50, 80, 100 비용의 프로젝트를 선택)

import java.util.Arrays;

public class ProjectBudgetOptimization {
    public static void main(String[] args) {
        int[] projects = {100, 200, 50, 80, 30};
        int budget = 300;
        System.out.println(maxProjects(projects, budget));
    }

    public static int maxProjects(int[] projects, int budget) {
        // 프로젝트 비용을 오름차순으로 정렬
        Arrays.sort(projects);

        // 이진 탐색을 위한 초기 설정: 시작 인덱스 left, 끝 인덱스 right
        int left = 0, right = projects.length;

        // 이진 탐색 시작
        while (left < right) {
            // 중간 인덱스 mid를 찾음
            int mid = left + (right - left) / 2;
            int sum = 0;

            // mid 개수의 프로젝트 비용 총합을 계산
            for (int i = 0; i < mid; i++) {
                sum += projects[i];
            }

            // 현재 예산으로 mid 개수의 프로젝트를 할 수 있는지 확인
            if (sum <= budget) {
                // 가능하면 더 많은 프로젝트를 시도하기 위해 left를 증가
                left = mid + 1;
            } else {
                // 불가능하면 프로젝트 개수를 줄이기 위해 right를 감소
                right = mid;
            }
        }

        // 가능한 최대 프로젝트 수 반환
        return left;
    }
}

1 정렬: 먼저, 프로젝트 비용 배열을 오름차순으로 정렬한다.

2 탐색 범위 설정: 탐색할 범위를 설정한다. 이 경우, 가능한 프로젝트의 최소 개수(0)부터 최대 개수(배열의 길이)까지로 설정한다.

3 이진 탐색 시작:

탐색 범위 내에서 중간 지점(mid)을 찾는다. 이 mid 값은 현재 고려하고 있는 프로젝트의 개수를 나타낸다.
mid 개수의 프로젝트를 수행할 때 필요한 총 비용을 계산한다.

4 결정 및 범위 조정:

계산된 총 비용이 주어진 예산 이하라면, 더 많은 프로젝트를 수행할 수 있을지 확인하기 위해 탐색 범위의 왼쪽 부분(즉, left = mid + 1)을 조정한다.
만약 총 비용이 예산을 초과한다면, 너무 많은 프로젝트를 고려하고 있는 것이므로, 탐색 범위의 오른쪽 부분(즉, right = mid)을 줄여서 프로젝트 개수를 감소시킨다.

5 반복: 이 과정을 left < right일 때까지 반복한다. 이 과정은 가능한 최대 프로젝트 수를 찾거나, 모든 가능성을 탐색할 때까지 계속된다.

6 결과 반환: 최종적으로 left는 주어진 예산으로 가능한 최대 프로젝트 수를 나타낸다.

이진 탐색을 사용함으로써, 우리는 선형적으로 모든 가능한 프로젝트 수를 확인하는 대신, 효율적으로 탐색 범위를 줄여나가며 최적의 해답을 빠르게 찾을 수 있다.