[백준] 1920_수찾기 / 이진탐색 binarySearch

 

 

Sliver

 

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다.

다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다.

다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다.

다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다.

모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

 

풀이

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N1 = Integer.parseInt(br.readLine());
        int[] arr = new int[N1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N1; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 이진탐색을 위해 오름차순 정렬을 해준다. 
        Arrays.sort(arr);
        int N2 = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N2; i++){
            int num = Integer.parseInt(st.nextToken());
            sb.append(binarySearch(arr, num)?1:0).append("\n");
        }
        System.out.print(sb);
        br.close();
    }

    public static boolean binarySearch(int[] arr, int target){
        int s = 0, e = arr.length-1;
        int index = 0;
        while(s <= e){
            index = (s+e)/2;
            if(arr[index] == target) return true;
            if(arr[index] < target) s = index +1;
            else if (arr[index] > target) e = index - 1;
        }
        return false;
    }
}

 

 

 

---

 

이진탐색 binarySearch

정렬된 배열에서 특정 값을 찾기 위해 사용되는 효율적인 알고리즘이다. 

탐색 범위를 반씩 줄여 나가기 때문에 시간 복잡도가 O(logN)으로 매우 빠르다. 

 

 

동작 원리

1. 배열의 중간 요소를 선택한다. 
2. 중간 요소와 찾고자 하는 값을 비교한다. 
3. 검색 범위를 반복적으로 절반으로 줄이며 위 과정을 반복한다. 

시간복잡도

• 최선, 평균, 최악의 경우: O(log n)

 

---

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