[ 알고리즘 ] 이진탐색 Binary Search

 

백이진

 

이진탐색은 코테도 코테인데, 기본적으로 알고있어야 하는 알고리즘이다.

이진탐색 -   Binary Search

검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘

 

전제 조건 : 배열이 오름차순 정렬되어 있어야 한다!

 

좀 더 자세히 설명하면 정렬된 데이터 중 공간을 반씩 나눠 제거해 나가는 방식이다.

 

ex)

업다운 게임을 효율적으로 이기려면 범위의 절반씩 나눠가면서 탐색을 하는 그런 느낌

 

시간 복잡도는 O(Log N)으로 일반적인 탐색 O(N)보다 빠르고, 데이터가 많아질수록 차이는 심해진다.

 

velog.io/@devjade/이진탐색-binary-search

 

자바에서는 이진탐색을 메서드로 제공한다.

//배열
Arrays.binarySearch()

//리스트
Collections.binarySearch()

 

여기서 두 메서드들의 리턴값을 알아보자!

만약에 값이 배열안에 있다면, 그 값의 위치(인덱스)를 출력하고,

배열에 없다면,  - (insertion point + 1)을 반환한다. 여기서 insertion point는 그 요소가 리스트에 삽입될 위치입니다.

 

ex A = [ 1, 2, 3, 4, 5 ]

-1을 탐색하면 -1은 존재하지 않고, 삽입 될 위치는 리스트의 맨 앞 0이기 때문에  -(0 +1) = -1을 출력한다.

7을 탐색하면 삽입될 위치는 리스트 맨 뒤 5이기 때문에 -( 5 +1 ) = -6을 출력한다.

---

문제 - 백준 1920번 수 찾기

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을 출력한다.

 

예제 입력 1 

5
4 1 5 2 3
5
1 3 7 9 5

 

예제 출력 1 

1
1
0
0
1

---

문제풀이

간단하게 자바의 Arrays.binarySearch로 구현했다.

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[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        // 오름차순 정렬
        Arrays.sort(A);

        int M = Integer.parseInt(br.readLine());
        int[] result = new int[M];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());
            //result[i] = binarySearch(A, target, 0, A.length - 1) > -1 ? 1 : 0;
            result[i] = Arrays.binarySearch(A, target) > -1 ? 1 : 0;
//            매개변수:
//                  a: 정렬된 배열입니다. 배열이 정렬되어 있어야만 정확한 결과를 보장합니다.
//                  key: 배열에서 검색할 값입니다.
//            반환 값:
//                  메서드는 배열에서 key 값의 인덱스를 반환합니다. 만약 key 값이 배열에 존재하지 않으면 음수 값을 반환합니다. 반환된 음수 값의 절댓값에 1을 빼면 key가 삽입될 위치를 알 수 있습니다.
        }

        for (int r : result) {
            System.out.println(r);
        }
    }

}

 

코드설명

오름차순으로 먼저 배열을 정렬해주고

Arrays.sort(A);

각각의 target에 대하여 Arrays.binarySearch를 해주는데,

이때 매개변수로 배열 A와 target이 들어가는데,

반환값으로 key값의 인덱스를 반환한다. 삼항연산자를 사용해서 key값이 존재하면 1을 없으면 0을 출력한다.

for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());
            //result[i] = binarySearch(A, target, 0, A.length - 1) > -1 ? 1 : 0;
            result[i] = Arrays.binarySearch(A, target) > -1 ? 1 : 0;
//            매개변수:
//                  a: 정렬된 배열입니다. 배열이 정렬되어 있어야만 정확한 결과를 보장합니다.
//                  key: 배열에서 검색할 값입니다.
//            반환 값:
//                  메서드는 배열에서 key 값의 인덱스를 반환합니다. 만약 key 값이 배열에 존재하지 않으면 음수 값을 반환합니다. 반환된 음수 값의 절댓값에 1을 빼면 key가 삽입될 위치를 알 수 있습니다.
        }