[백준 1920번 수 찾기 Java] 수 찾기 이진 탐색 BinarySearch

이진 탐색은 원하는 key값을 찾을 때까지 중앙값을 기준으로 탐색 구간을 반씩 줄여나가기 때문에 시간복잡도 O(log(n))을 가진다.

예를 들어, 64의 자료 개수를 탐색한다면 6번의 과정으로 탐색을 수행해낼 수 있다는 이야기다 

 

이진 탐색을 하는 방법은 2가지 있다

하나는 재귀를 이용한 이진탐색, 다른 하나는 반복문을 이용한 이진탐색이다.

 

백준에서 두 코드의 시간을 객관적으로(?)  비교해 보았다.

반복문이 더 빠를 거라고 예상했고, 결과도 그러하였다 

 

아래 코드는 반복문을 이용한 이진 탐색의 시행이다.

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int m = Integer.parseInt(br.readLine());
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < m; i++) {
            int key = Integer.parseInt(st.nextToken());
            int lo = 0;
            int hi = n - 1;
 
           sb.append(BinarySearch(arr,0,n-1,key)).append("\n");
        }
        System.out.println(sb);
    }
 
    public static int BinarySearch(int[] arr, int lo, int hi, int key){
        while (lo <= hi) { //lo가 hi보다 작거나 같으면 계속해서 
 
            int mid = (lo + hi) / 2;
            if (arr[mid] == key) {
                return 1;
            }
            else if (arr[mid] < key)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        return 0;
    }
}

아래는 결과이다

---

아래는 재귀를 이용한 이진탐색의 시행이다

 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int m = Integer.parseInt(br.readLine());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int key = Integer.parseInt(st.nextToken());
            sb.append(BinarySearch(arr, 0, n - 1, key)).append("\n");
        }
        System.out.println(sb);
    }
 
    public static int BinarySearch(int[] arr, int lo, int hi, int key) {
 
        if (lo > hi) //lo가 hi보다 커진다면 더 탐색이 실패이므로 0을 반환!
            return 0;
 
        int mid = (lo + hi) / 2;
 
        if (arr[mid] == key)
            return 1; // 찾은 경우 1을 반환
        else if (arr[mid] < key)
            return BinarySearch(arr, mid + 1, hi, key);
        else
            return BinarySearch(arr, lo, mid - 1, key);
 
    }
}

아래는 결과이다

 

개인적으로 재귀를 이용한 구현을 더 선호하는 편이다.