이진 탐색

백준 10815번을 자바를 이용해 풀어보았다.
문제 링크 첨부한다.
https://www.acmicpc.net/problem/10815

가장 기본적인 이진 탐색

문제 조건을 보면 완전 탐색을 할 경우 50만 * 50만 이 worst case scenario 다. 총 2500억 개의 case 를 계산해야 하니까 시간 초과가 날 것이 분명했다. 이진 탐색을 이용해야겠다고 생각한 부분이다.

바로 코드로 옮겨서 작성했지만 첫 시도에는 틀렸다. 코드를 작성할 때 딱 한 부분이 좀 미심쩍었는데 그 부분을 고쳐보니 바로 해결이 됐다.

l<r? l<=r?

while 문을 사용해서 이진 탐색을 진행했는데 조건문에 등호를 넣어야할지 빼야할지 잠시 고민이 됐다. 정확히 개념이 머릿속에 자리 잡지 못했다는 것을 알 수 있었다.

예시 상황을 하나 생각해보자. 찾으려는 target 값이 우리가 갖고 있는 정렬된 배열 안에 존재하지 않는 경우를 가정하자.

현재 l 값은 19, r 값은 20 이라고 한다면 mid 는 (19+20)/2 의 결과로 또다시 19가 될 것이다. 우리의 target은 20번 인덱스에 위치해있다면 mid 값이 또다시 19가 나왔기 때문에 결국 target값에 이르지 못한 채로 while 문이 종료될 것이다. 그렇다면 flag = false 로 유지될 것이기 때문에 우리가 가진 배열 안에 target 값이 없다고 판단되는 것이다.

which is 잘못된 결과...

따라서 반드시 등호가 조건문 안에 포함되어야 한다!!

다음은 내가 제출한 코드다.

import java.util.*;

public class boj10815{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] myCard = new int[N];

        for(int i=0; i<N; i++)
            myCard[i] = sc.nextInt();

        int M = sc.nextInt();
        int[] doIHave = new int[M];

        for(int i=0; i<M; i++)
            doIHave[i] = sc.nextInt();

        Arrays.sort(myCard);
        for(int i=0; i<M; i++){
            int tmp = 0;
            if(check(myCard, doIHave[i]))    tmp = 1;
            System.out.print(tmp + " ");
        }
    }

    static boolean check(int[] myCard, int target){
        boolean flag = false;
        int l = 0, r = myCard.length-1;

        while(l<=r){ // 등호도 꼭 들어가야 한다는 점!
            int mid = (l + r)/2;

            if(myCard[mid]<target){
                l = mid + 1;
            }
            else if(myCard[mid]>target){
                r = mid - 1;
            }
            else{
                flag = true;
                break;
            }
        }

        return flag;
    }
}