| Binary Search

• 📢 정렬되어 있는 집합에서 원하는 값을 찾는 효율적인 탐색 방법

🦕  정렬된 N개의 원소를 가진 배열에서 X라는 값이 존재하는지 알고 싶다면?

boolean isExist(int[] arr, int X) {
	// arr 배열에 x라는 값이 있는가?
	// 있다면 return true;
	// 없다면 return false;
}

🦖 가장 쉬운 방법은 순차적으로 찾는거임.

모든 원소를 차례대로 탐색하므로 아래 코드의 시간복잡도는 O(N)임.

boolean isExist(int[] arr, int X) {
        for(int a: arr)  
            if (a == X) return true;
        return false;
    }

이보다 빠른 효율적인 탐색방법은 없을까?

모든 원소를 보지 않아도 탐색하는 방법이 필요함!

만약 arr[] 이 정렬되어 있다면??

🦖 답이 될 수 있는 범위 [L:R] 중 임의의 값 $a_M$에 대해
$a_M$과 찾는 값 X의 대소관계에 따라 범위를 줄일 수 있음.

위 그림을 예로 들어보자.

만약 $a_M$이 X보다 작다면( $a_M$ < X) X는 [L : M] 범위에 존재할 수 없음.

이때 조사 범위는 [M+1 : R]로 좁힐 수 있음.

반대로 $a_M$이 X보다 크다면( $a_M$ > X) X는 [M : R] 범위에 존재할 수 없음.

이때 조사 범위는 [L : M-1]로 좁힐 수 있음.

    boolean isExist(int[] arr, int X) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m= (l + r) / 2;
            if (arr[m] < X) l = m + 1;
            else if (arr[m] > X) r = m - 1;
            else return true;
        }
        return false;
    }

시간복잡도도 한번 알아보자.

첫 탐색 범위는 N 이지만, 이는 점차 2의 배수로 줄어듦.

두 번째 탐색 N / 2

세 번째 탐색 N / $2^2$

…

logN 번째 탐색 범위는 N / $2^{logN}$ = N / N

탐색 범위; 값이 1개 이하로 남을 때까지 탐색하므로

따라서 전체 시간복잡도는 O(logN) 임을 알 수 있음.

정리

• Binary Search는 정렬된 집합에서 원하는 값을 찾는 효율적인 방법임.

  집합 전체를 탐색하지 않기 때문에 시간 복잡도도 줄일 수 있음.

  O(N) → O(logN)

1. 원하는 값이 존재할 수 있는 범위 초기화.
   일반적으로 집합의 전체 범위가 첫 조사 범위임.

2. 현재 유효한 범위의 중앙값과 찾는 값을 비교하여 조사 범위를 좁힘.
   중앙값과 같다면 해당 값을 찾은 것이므로 종료.
   중앙값이 찾는 값보다 작다면 조사 범위를 중앙값보다 큰 범위로 좁힘.
   중앙값이 찾는 값보다 크다면 조사 범위를 중앙값보다 작은 범위로 좁힘.

3. 유효 범위가 남지 않을 때까지 찾지 못했다면, 해당 값은 존재하지 않음.

아래는 binary Search를 활용한 두 문제임.

binary Search는 특정 값을 찾는 것 이외에도 활용되는 곳이 많기 때문에 공부해두면 좋음!

Baekjoon 대표 문제

🦕 [1920] 수 찾기

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];

        for(int i = 0; i < N; i ++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        int  M = sc.nextInt();

        for(int i = 0; i < M; i ++) {
            int idx = Arrays.binarySearch(arr, sc.nextInt());
            System.out.println(idx >= 0 ? "1" : "0");
        }
    }
}

🦕 [14425] 문자열 집합

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

1. Set을 이용한 풀이

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int ans = 0;
        
        Set<String> set = new HashSet<>();  
        
        for (int i = 0; i < N; i++) set.add(sc.next());

        for (int i = 0; i < M; i++) {
            if (set.contains(sc.next())) ans++;
        }

        System.out.println(ans);
    }
}

2. binary search를 이용한 풀이(함수 구현, 내장함수 사용)

package binarySearch;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class baekjoon_14425 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int ans = 0;

        String[] wordArr = new String[N];
        String [] compareArr = new String[M];

				for(int i = 0; i < N; i++) {
            compareArr[i] = sc.next();
        }

        for(int i = 0; i < M; i++) {
            wordArr[i] = sc.next();
        }

        Arrays.sort(compareArr);

        for(int i = 0; i < N; i++) {
            if (Arrays.binarySearch(compareArr, wordArr[i]) >= 0)
                ans++;
//            if (isExisted(compareArr, wordArr[i]))  ans++;
        }
        System.out.println(ans);
    }
    
        public static boolean isExisted(String[] arr, String key) {
        int l = 0, r = arr.length - 1;
        while(l <= r) {
            int m = (l + r) / 2;
            int compareResult = arr[m].compareTo(key);
            if (compareResult < 0) l = m + 1;
            else if (compareResult > 0) r = m - 1;
            else return true;
        }
        return false;
    }
}

---

[fastcampus] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online.