이분 탐색 (Binary Search)

이분 탐색 (Binary Search)

이분 탐색 알고리즘의 큰 골자를 이루는 로직은

 

1. 오름차순으로 정렬 되어 있는 자료 구조에서 특정값을 찾을 때,

2. 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것이다.

 

 

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

1920번: 수 찾기

위 문제를 이분 탐색으로 풀어보았다.

 

배열의 중간값(mid)을 기준으로

target 값 보다 작으면 binarySearch(start ~ mid-1)

target 값 보다 크면 binarySearch(mid+1 ~ end) 를 호출한다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static int[] a;
    static boolean[] c;
    static int n, m;
    static StringTokenizer st;
    static StringBuilder sb;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = stoi(br.readLine());
        a = new int[n];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = stoi(st.nextToken());
        }
        Arrays.sort(a);
 
        m = stoi(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            System.out.println(binarySearch(0, n - 1, stoi(st.nextToken())));
        }
    }
 
    static int binarySearch(int start, int end, int target) {
        if (start > end)
            return 0;
        int mid = (start + end) / 2;
        if (target == a[mid])
            return 1;
        if (target < a[mid]) {
            return binarySearch(start, mid - 1, target);
        } else {
            return binarySearch(mid + 1, end, target);
        }
    }
 
    static int stoi(String s) {
        return Integer.valueOf(s);
    }
}