[Java] baekjoon 1920 : 수 찾기 / 이분 탐색

문제 

---

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

1920번: 수 찾기

해결 

---

이분 탐색 (Binary Search)

정렬돼있는 배열에서 탐색 범위를 반씩 줄여 가며 목푯값을 찾는 탐색 방법이다. 목푯값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에 매 단계에서 검색해야 할 범위를 반으로 줄일 수 있다.

ex 1) 75를 탐색하는 경우

fir : 탐색 범위의 첫 인덱스
last : 탐색 범위의 마지막 인덱스
mid : 탐색 범위의 중앙값의 인덱스, (fir + last) / 2

 

index	0	1	2	3	4	5	6	7	8
value	15	25	35	45	55	65	75	85	95

fir = 0

last = 8

mid = 4

중앙값 = 55

 

중앙값이 목푯값보다 작으므로 첫 인덱스 값을 mid + 1로 조정해 탐색 범위를 반으로 좁힌다.

 

index	0	1	2	3	4	5	6	7	8
value	15	25	35	45	55	65	75	85	95

fir = 5

last = 8

mid = 6

중앙값 = 75

 

중앙값과 목푯값이 일치하여 탐색 종료

일일이 비교하는 방법보다 훨씬 빨리 목푯값 탐색 성공

ex 2) 25를 탐색하는 경우 

fir : 탐색 범위의 첫 인덱스
last : 탐색 범위의 마지막 인덱스
mid : 탐색 범위의 중앙값의 인덱스, (fir + last) / 2

 

index	0	1	2	3	4	5	6	7	8
value	15	25	35	45	55	65	75	85	95

fir = 0

last = 8

mid = 4

중앙값 = 55

 

중앙값이 목푯값보다 크므로 마지막 인덱스 값을 mid - 1로 조정해 탐색 범위를 반으로 좁힌다.

 

index	0	1	2	3	4	5	6	7	8
value	15	25	35	45	55	65	75	85	95

low = 0

high = 3

mid = 1

중앙값 = 25

 

중앙값과 목푯값이 일치하여 탐색 종료

일일이 비교하는 방법보다 훨씬 빨리 목푯값 탐색 성공

구현 

---

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int[] arrN = new int[n];
        for (int i = 0; i < n; i++) {
            arrN[i] = sc.nextInt();
        }
        Arrays.sort(arrN); // 이분 탐색을 위해 정렬
 
        int m = sc.nextInt();
        int[] arrM = new int[m];
        for (int i = 0; i < m; i++) {
            arrM[i] = sc.nextInt();
            System.out.println(binarySearch(arrN, arrM[i]));
        }
 
    }
 
    public static int binarySearch(int[] arr, int num) { // 이분 탐색 구현
        int fir = 0;
        int mid = 0;
        int last = arr.length - 1;
        while (fir <= last) {
            mid = (fir + last) / 2;
            if (arr[mid] == num) {
                return 1; // 배열에 수가 존재하면 1 출력
            } else if (arr[mid] < num) {
                fir = mid + 1;
            } else if (arr[mid] > num) {
                last = mid - 1;
            }
        }
        return 0; // 배열에 수가 존재하지 않으면 0 출력
    }
 
}

결과 

---