[이코테] 이진탐색(Binary Search)

이진탐색(Binary Search)

정렬된 데이터에서 탐색 범위를 절반씩 줄여나가면서 검색 값을 찾는 알고리즘

탐색할 때마다 원소의 개수가 절반으로 줄어들기 때문에 속도가 빠르다

시간복잡도 - O(log N)

1. 배열의 중간값(mid)을 구한다.
2. 중간값과 검색 값(target)을 비교한다.
      - 중간 값과 검색 값이 같으면 종료(mid == target)
      - 중간 값보다 검색 값이 크면 중간 값 기준 오른쪽 구역을 탐색(mid < target)
      - 중간 값보다 검색 값이 작으면 중간 값 기준 왼쪽 구역을 탐색(mid > target)

---

예제 1) 부품찾기

전자 매장에 부품이 N개 있고, 각 부품은 정수 형태의 고유한 번호가 있다. 어느날 손님이 M개 종류의 부품을 대량으로 구매를 요청해서 견적서를 작성해야할 때, 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해라.

부품이 있으면 yes, 없으면 no 출력

 

문제 해설

• 입력받은 매장의 부품 n개를 오름차순 정렬한 후, 이진탐색을 해서 손님이 찾는 부품이 있는지 탐색한다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static boolean binary_search(int[] store, int x, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            if (store[mid] == x) {
                return true;
            } else if (store[mid] < x) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return false;
    }

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

        int n = Integer.parseInt(br.readLine());    //가게에 있는 부품의 개수
        int[] store = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            store[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(store); //가게에 있는 부품들 정렬

        int m = Integer.parseInt(br.readLine());    //손님이 요청한 부품의 개수
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int customer = Integer.parseInt(st.nextToken());
            boolean result = binary_search(store, customer, 0, n - 1);
            if(result) {
                System.out.print("yes ");
            } else {
                System.out.print("no ");
            }
        }
    }
}

 

 

 

 

 

예제 2) 떡볶이 떡 만들기 

길이가 다른 떡들을 높이가 H인 절단기로 한 번에 절단한다.

예를 들어 19, 14, 10 17 cm인 떡이 있고 절단기 높이를 15cm로 지정하면, 자른 뒤 떡의 높이는 15, 14, 10 15cm이고, 잘린 떡의 길이는 4, 0, 0, 2 cm이다. 이 때 손님은 6cm만큼의 떡을 가져간다.

손님이 왔을 때 요청한 총 길이가 M일 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램을 작성하시오.

 

문제 해설

• 절단기의 높이 범위 값을 0 ~ (가장 긴 떡의 길이) 로 해서 이진 탐색을 통해서 절단기 높이의 최대값을 구한다.
• mid = 절단기의 높이
• sum = N개의 떡을 절단기로 잘라낸 길이를 모두 합한 것
• sum < target(m) 일 경우, 끝점을 mid-1로 변경
• sum >= target(m)일 경우,  
  • 현재 절단기의 높이인 mid를 result에 저장(현재 절단기 높이보다 더 큰 값이 조건에 성립할 수도 있기 때문에 result에 저장하고 다음을 수행)
  • 시작점을 mid+1로 변경

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

public class Main {

    public static int binary_search(int[] array, int target, int start, int end) {
        int result = 0;

        while (start <= end) {
            int mid = (start + end) / 2;

            int sum = 0;
            //잘랐을 때 떡의 양 계산
            for (int i : array) {
                if (i > mid) {
                    sum += (i - mid);
                }
            }

            if (sum < target) {
                end = mid - 1;
            } else {
                result = mid;
                start = mid + 1;
            }
        }
        return result;
    }


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] array = new int[n];
        int max = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
            max = Math.max(array[i], max);
        }

        System.out.println(binary_search(array, m, 0, max));
    }
}

---

[참고]

이것이 취업을 위한 코딩 테스트다 with 파이썬