[백준] 1920 수찾기

[S4] 수 찾기 
__💡이분탐색 (Binary Search) __
이분탐색을 이용한 배열에서 수 찾기 문제 __
https://www.acmicpc.net/problem/1920

 

문제보기

 

---

🙄어떻게 풀까?

이분탐색 방식으로 풀이 진행

1. 이분탐색을 위해 배열을 정리하고
2. 정렬된 배열에서 이분탐색을 통해 값이 있는지 확인하는 과정을 거치면 된다.

---

1. input 값 배열에 담고 정렬해두기

이분탐색 진행을 위해서는
배열의 정렬은 반드시 선행되어야 함

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

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

 

---

 

2. 이분탐색 이해하기

위 그림과 같이 들어온 num 과 mid 인덱스에 해당하는 배열을 비교한 후

해당 값의 크기 비교를 통해 min, max 값을 변경하며 이분탐색을 통해 원하는 값을 찾아나간다.

static int solution(int num){
    int result = 0;

    int min = 0;
    int max = arr.length - 1;

    while (min <= max){
        int mid = (min + max) / 2;
        if (num == arr[mid]){
            result = 1;
            break;
        } else if (num > arr[mid]) {
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }
    return result;
}

---

 

⭐ 전체코드 자바

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

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

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

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(solution(num)).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static int solution(int num){
        int result = 0;

        int min = 0;
        int max = arr.length - 1;

        while (min <= max){
            int mid = (min + max) / 2;
            if (num == arr[mid]){
                result = 1;
                break;
            } else if (num > arr[mid]) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return result;
    }
}