<stdio.han>

[문제 링크]

https://www.acmicpc.net/problem/19637

[난이도]

- Silver 3

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M;
    static int[] power;
    static String[] title;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        power = new int[N];
        title = new String[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            title[i] = st.nextToken();
            power[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(br.readLine());
            binarySearch(key);
        }
        System.out.println(sb);
    }

    static void binarySearch(int key) {
        int left = 0;
        int right = N;
        int index = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (key <= power[mid]) {
                right = mid - 1;
                index = mid;
            } else if (key > power[mid]) {
                left = mid + 1;
            }
        }
        sb.append(title[index]).append("\n");
    }
}

[풀이]

찾으려는 key 값이 mid보다 작거나 같을 때마다 index를 갱신해준다. 그리고 while문이 끝났을 경우 갱신해왔던 index를 형식에 맞게 출력해준다.

[문제 링크]

https://www.acmicpc.net/problem/4158

[난이도]

- Silver 5

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M, answer;
    static int[] arr;

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

        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            if (N == 0 && M == 0) break;

            arr = new int[N];
            answer = 0;

            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(br.readLine());
            }

            for (int i = 0; i < M; i++) {
                int key = Integer.parseInt(br.readLine());
                if (binarySearch(key)) {
                    answer++;
                }
            }

            System.out.println(answer);
        }

        br.close();
    }

    static boolean binarySearch(int key) {
        int left = 0;
        int right = arr.length - 1;

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

            if (key == arr[mid]) {
                return true;
            } else if (key < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

[풀이]

가장 기본적인 이분탐색 코드이다.

key 값을 찾을 때마다 answer++를 한 후 출력해준다.

[문제 링크]

https://www.acmicpc.net/problem/2417

[난이도]

- Silver 4

[알고리즘]

- 이분 탐색

[코드]

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

public class Main {
    static long n, answer = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Long.parseLong(br.readLine());
        binarySearch(n);
        System.out.println(answer);
    }

    static void binarySearch(long key) {
        long left = 0;
        long right = key;
        while (left <= right) {
            long mid = (left + right) / 2;
            if (key <= Math.pow(mid, 2)){
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
}

[풀이]

이분탐색 알고리즘 보다 타입맞추는게 더 까다로웠다.

(mid * mid) 로 계산하면 long의 범위를 넘어가 버려 정답을 맞출 수 없다.

Math.pow(mid, 2) 는 반환값이 double 이기때문에 이를 사용해야한다.

[문제 링크]

https://www.acmicpc.net/problem/1654

[난이도]

- Silver 2

[알고리즘]

- 파라메트릭 서치

[코드]

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

public class Main {
    static int K, N;
    static long left = 1, right = Integer.MIN_VALUE;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new int[K];

        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            right = Math.max(right, arr[i]);
        }

        parametricSearch();

        br.close();
    }
    static void parametricSearch() {
        while (left <= right) {
            long mid = (left + right) / 2;
            long LAN = 0;
            for (int i = 0; i < arr.length; i++) {
                LAN += (arr[i] / mid);
            }
            if (LAN>=N){
                left = mid + 1;
            } else if (LAN < N) {
                right = mid - 1;
            }
        }
        System.out.println(right);
    }
}

[풀이]

- left, right, mid 를 long으로 설정해주어야 한다.

- left의 최소값이 1이어야 한다. 그렇지 않으면 divide by zero 오류가 발생한다. 예를들어 모든 가지고있는 랜선의 길이가 1이고 left가 0일 경우 mid가 0이 된다.

https://www.acmicpc.net/problem/7795

[난이도]

- Silver 3

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int T, N, M, answer;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            answer = 0;
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            arr = new int[N];
            M = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);

            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int key = Integer.parseInt(st.nextToken());
                answer += binarySearch(key);
            }

            System.out.println(answer);
        }

    }
    static int binarySearch(int key) {
        int left = 0;
        int right = N - 1;
        while (left <= right) { // left가 right를 넘어서기 전까지 반복
            int mid = (left + right) / 2;
            if (key >= arr[mid]) { // key가 mid 와 같거나 클 경우
                left = mid + 1;
            } else if (key < arr[mid]) { // key가 mid 보다 작을 경우
                right = mid - 1;
            }
        }
        // left가 right를 넘어감
        return N - right - 1; 
    }
}

[풀이]

for문을 적게 사용하고 싶어서 B를기준으로 이분탐색을 했다. A가 B를 먹을 수 있는 쌍을 구하는게 아닌 B가 A에게 먹힐 수 있는 쌍을 구했다.

https://www.acmicpc.net/problem/10816

[난이도]

- Silver 4

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M;
    static int[] arr, answer;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        M = Integer.parseInt(br.readLine());
        answer = new int[M];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            int tmp = upperBound(key) - lowerBound(key);
            bw.write(tmp + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    /**
     * key 값이 배열 내에 없을 경우 lowerBound, upperBound 둘다 key 바로 앞의 숫자를 찾게된다. 결국 n - n = 0이 된다.
     */

    static int lowerBound(int key) {
        int left = 0;
        int right = N;
        while (left < right) { // left 와 right가 같아질 때 까지 반복
            int mid = (left + right) / 2; // 중간 위치

            /**
             * key 값이 중간 위치의 값보다 작거나 같을 경우
             * 중복 원소일 경우 가장 왼쪽값을 선택
             */
            if (key <= arr[mid]) {
                right = mid;
            } else { // key가 중간 값보다 '클' 경우. key > arr[mid]
                left = mid + 1;
            }
        }
        return left;
    }

    static int upperBound(int key) {
        int left = 0;
        int right = N;
        while (left < right) {// left 와 right가 같아질 때 까지 반복
            int mid = (left + right) / 2; // 중간 위치
            if (key < arr[mid]) { // key가 중간 값보다 작을 경우
                right = mid;
            } else { // key가 중간 보다 '크거나' '같을' 경우 key >= arr[mid]
                left = mid + 1;
            }
            // left가 right를 넘어서는 순간 종료된다 == left가 key의 바로 다음 인덱스가 되는순간 종료된다.
        }
        return left;
    }
}

[풀이]

배열안에 중복값이 들어있을 경우가 존재하기 때문에 그 ( 중복값의 가장 왼쪽 인덱스 - 중복값의 가장 오른쪽의 다음 인덱스 ) 를 계산해주어야 한다.

leftBound

찾으려는 key값이 중간 값보다 작거나 클 경우 right 값이 mid가 되고 그 이외의 경우에는 left = mid + 1이 된다.  이를 반복할 경우 left 와 right가 key값들의 가장 왼쪽인덱스가 된다.

rightBound

찾으려는 key값이 중간 값보다 작을 경우 right = mid가 되고 그 외의 경우에는 left = mid + 1이 된다. 이를 반복하다 보면 right는 key값들의 가장 오른쪽 인덱스, left는 key값들의 가장 오른쪽의 다음 인덱스가 된다.

만약 찾으려는숫자가 없을 경우 lowerBound, upperBound 둘다 배열 중 key값을 초과하는 값중 첫 인덱스를 가리키게 된다.

[출처]

https://st-lab.tistory.com/267

https://www.acmicpc.net/problem/2776

[난이도]

- Silver 4

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int T, N, M;
    static int[] noteOne;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            noteOne = new int[N];
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                noteOne[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(noteOne);
            M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");
            for (int k = 0; k < M; k++) {
                int num = Integer.parseInt(st.nextToken());
                if (binarySearch(num)) {
                    bw.write("1\n");
                } else {
                    bw.write("0\n");
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static boolean binarySearch(int num) {
        int left = 0;
        int right = N - 1;
        while (left <= right) { // left인덱스가 right인덱스를 넘어가기 전 까지 반복
            int mid = (left + right) / 2;
            if (num > noteOne[mid]) {
                left = mid + 1;
            } else if (num < noteOne[mid]) {
                right = mid - 1;
            } else { // num == noteOne[mid]
                return true;
            }
        }
        return false;
    }
}

[풀이]

가장 기본적인 이분탐색 문제이다. 중요한 점은 출력 시 System.out.println()을 하면 시간초과가 발생한다. 효율이 안좋기 때문에 BufferedWriter를 사용해주자.

https://www.acmicpc.net/problem/10815

[난이도]

- Silver 5

[알고리즘]

- 이분탐색

[코드]

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

public class Main {
    static int N, M;
    static int[] sangArr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        sangArr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            sangArr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sangArr); // 오름차순 정렬

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (binarySearch(num)) {
                bw.write("1 ");
            } else {
                bw.write("0 ");
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static boolean binarySearch(int num) {
        int leftIndex = 0;
        int rightIndex = N - 1;
        while (leftIndex <= rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;
            int mid = sangArr[midIndex];

            if (num < mid) { // 찾으려는 숫자가 더 작을경우 rightIndex를 mid-1 로 설정
                rightIndex = midIndex - 1;
            } else if (num > mid) { // 찾으려는 숫자가 더 클경우 leftIndex mid+1 로 설정
                leftIndex = midIndex + 1;
            } else { // 숫자가 있을 경우
                return true;
            }
        }
        return false; // 숫자가 없을 경우
    }
}

[풀이]

일반적인 이분탐색 문제이다. midIndex와 mid값이 다르기 때문에 탐색은 인덱스 기준으로하고 찾는 숫자는 arr[midIndex]로 찾는다.