[Do it] 알코테 자바 10일차

_06-4 이진 탐색 (Binary Search)

이진 탐색은 정렬된 데이터에서 원하는 값을 효율적으로 찾아내는 탐색 알고리즘입니다.
단순히 처음부터 끝까지 순차적으로 탐색하는 것이 아니라, 중앙값을 기준으로 탐색 범위를 절반씩 줄여 나가는 방식을 사용합니다.

---

1. 특징

1. 정렬된 배열에서만 사용 가능
   이진 탐색을 사용하기 위해서는 데이터가 오름차순 또는 내림차순으로 정렬되어 있어야 합니다.
2. 시간 복잡도
   • 최악, 평균: O(log N)
   • 순차 탐색과 비교 시 데이터가 많을수록 효율이 크게 증가합니다.
3. 탐색 방식
   중앙값(mid)과 찾고자 하는 값(target)을 비교합니다.
   • target == mid → 탐색 성공
   • target < mid → 왼쪽 절반 탐색
   • target > mid → 오른쪽 절반 탐색
     이 과정을 반복합니다.

---

2. 순서도

[시작]
   │
   ▼
[배열 정렬 확인]
   │
   ▼
[low = 0, high = n-1 설정]
   │
   ▼
[low <= high ?]
 ┌───┴───┐
 │       │
 ▼       ▼
[중앙값 mid = (low+high)/2 계산]
 │
 ▼
[target == arr[mid]?]
 ┌───┴───┐
 │       │
 ▼       ▼
[찾음]   [target < arr[mid]?]
           ┌───┴───┐
           │       │
           ▼       ▼
        [high=mid-1] [low=mid+1]
           │       │
           └───────┘
           ▼
         반복

---

3. 예제 (Java)

public class BinarySearchExample {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (arr[mid] == target) {
                return mid; // 찾음
            } else if (arr[mid] < target) {
                low = mid + 1; // 오른쪽 절반 탐색
            } else {
                high = mid - 1; // 왼쪽 절반 탐색
            }
        }

        return -1; // 없음
    }

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

        int index = binarySearch(arr, target);
        System.out.println("Target 위치: " + index);
    }
}

---

4. 정리

• 이진 탐색은 정렬된 데이터에서만 사용 가능하며,
• 중앙값 비교로 탐색 범위를 절반씩 줄여 빠르게 원하는 값을 찾는 알고리즘입니다.
• 배열 길이가 커질수록 순차 탐색 대비 효율이 매우 높습니다.

---

__[032] 원하는 정수 찾기

백준 온라인 져지 1920번 https://www.acmicpc.net/problem/1920

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위해 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // N 입력
        int N = Integer.parseInt(br.readLine());
        
        // A 배열 입력
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        // 배열 정렬: 이진 탐색 전 필수
        Arrays.sort(A);
        
        // M 입력
        int M = Integer.parseInt(br.readLine());
        
        // 확인할 수 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());
            
            // 이진 탐색 결과 존재 여부 판단
            if (binarySearch(A, target)) {
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }
        
        // 결과 출력
        System.out.print(sb);
    }
    
    // 이진 탐색 함수: 배열 arr에서 target 존재 여부 반환
    static boolean binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            
            if (arr[mid] == target) {
                return true; // 찾음
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반 탐색
            } else {
                right = mid - 1; // 왼쪽 절반 탐색
            }
        }
        
        return false; // 존재하지 않음
    }
}

__[033] 블루레이 만들기

백준 온라인 져지 2343번 https://www.acmicpc.net/problem/2343

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 강의 수
        int M = Integer.parseInt(st.nextToken()); // 블루레이 수

        int[] lectures = new int[N]; // 강의 길이 배열
        st = new StringTokenizer(br.readLine());
        int maxLecture = 0; // 가장 긴 강의 길이
        int sumLecture = 0; // 모든 강의 합
        for (int i = 0; i < N; i++) {
            lectures[i] = Integer.parseInt(st.nextToken());
            maxLecture = Math.max(maxLecture, lectures[i]);
            sumLecture += lectures[i];
        }

        // 이진 탐색 범위: 가장 긴 강의 <= 블루레이 크기 <= 모든 강의 합
        int left = maxLecture; // 최소 블루레이 크기
        int right = sumLecture; // 최대 블루레이 크기
        int result = sumLecture; // 정답 초기화

        while (left <= right) {
            int mid = (left + right) / 2; // 현재 블루레이 용량 가정
            int count = 1; // 블루레이 개수, 최소 1개
            int sum = 0; // 현재 블루레이에 담긴 강의 길이 합

            for (int i = 0; i < N; i++) {
                if (sum + lectures[i] > mid) {
                    // 현재 블루레이에 강의를 담으면 용량 초과 -> 새 블루레이
                    count++;
                    sum = 0;
                }
                sum += lectures[i];
            }

            if (count <= M) {
                // M개 이하의 블루레이로 가능 -> 용량 줄여보기
                result = mid; // 최소 블루레이 크기 후보 갱신
                right = mid - 1;
            } else {
                // 블루레이 개수가 너무 많음 -> 용량 늘리기
                left = mid + 1;
            }
        }

        System.out.println(result);
    }
}

__[034] 배열에서 K번째 수 찾기

백준 온라인 져지 1300번 https://www.acmicpc.net/problem/1300

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        // 배열 크기 N 입력
        int N = Integer.parseInt(br.readLine());
        // K번째 수 입력
        int k = Integer.parseInt(br.readLine());
        
        // 이진탐색 범위: 최소값 1, 최대값 N*N
        int left = 1;
        int right = N * N;
        int answer = 0;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            int count = 0; // mid 이하의 수 개수 세기
            
            // mid 이하의 수를 곱셈표에서 계산
            for(int i = 1; i <= N; i++) {
                count += Math.min(mid / i, N); // i행에서 mid 이하인 수의 개수
            }
            
            // mid 이하의 수가 k보다 작으면 더 큰 수로 범위 이동
            if(count < k) {
                left = mid + 1;
            } else { // count >= k이면 mid 후보 저장 후 왼쪽 범위 탐색
                answer = mid;
                right = mid - 1;
            }
        }
        
        // K번째 수 출력
        System.out.println(answer);
    }
}