이분 탐색 ( Binary Search )

 

   주어진 탐색 배열

 

 

 

   Q) 찾아야 하는 값 key가 7로 주어졌다.

 

 

 

   일단 기본적으로 정렬이 된 배열이 필요하다. low는 1을 가리키는 인덱스 0, high는 17을 가리키는 인덱스 8이다.

 

 

 

  low와 how의 평균을 내어 가운데를 찍어본다. 9는 찾는 값이 아니다. key인 7보다 크다. 아래 영역으로 탐색하자.

 

 

 

  high는 9의 인덱스인 4에서 1을 빼서 3이 된다. low는 변경 없으므로 (0+3)/2 = 1이 된다. 인덱스 1의 값 3을 탐색

  답이 아니므로 다시 영역을 변경한다. 찾는 값 보다 작으므로 low 값을 +1 올려보자.

 

 

 

   아래 영역의 가운데를 찍어본다. key인 7보다 작다. 더 큰 영역으로 탐색하자.

 

 

 

   정답을 찾았다. true를 반환한다.

 

 

 

   구현적 측면

     - 하한과 상한의 평균 값과 키 값을 비교해 왼쪽의 하한선을 올리거나(↑) 오른쪽의 상한선을 내리게(↓) 된다.

     - 만약 key가 9이 되어, left > right인 상황이 오면 탐색이 끝났으므로 false가 반환된다.

   

 

 

 

백준 1920번 문제

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

1920번: 수 찾기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        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());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            // 이분 탐색
            if(search(Integer.parseInt(st.nextToken()))) sb.append(1).append('\n');
            else sb.append(0).append('\n');
        }
        System.out.print(sb);

    }
    public static boolean search(int key){
        int l = 0;
        int r = arr.length-1;

        while (l <= r){
            int center = (l + r) / 2;

            if(key < arr[center]){
                r = center - 1;
            }
            else if(key > arr[center]){
                l = center+1;
            }else{
                return true;
            }
        }
        return false;
    }
}

 

 

 

upperbound
찾는 값(key)과 같을 때 -> low가 mid(지금 탐색 중인 자리) 보다 하나 크게 된다. (초과)

찾는 값이 없을 때 -> 하나 큰 값을 답으로 가리키게 된다.

lowerbound
찾는 값(key)과 같을 때 -> high가 mid(지금 탐색 중인 자리)보다 하나 크게 된다. (이상)

찾는 값이 없을 때 -> 하나 큰 값을 답으로 가리키게 된다.