[JAVA] 백준_10815

[문제]

10815번: 숫자 카드 (acmicpc.net)

10815번: 숫자 카드

[알고리즘]

이분탐색을 이용하는 문제였다.

하나하나 다 확인해보는 선형탐색과는 달리, 이분탐색은 확인하려는 값이 중간값보다 큰지 작은지 확인하고 만약 크다면 / 작다면 중간값보다 작은 / 큰 값은 볼 필요가 없으므로 중간값보다 큰 / 작은 값만 놓고 이와같은 과정을 반복해서 탐색하는 방식이다.

예를 들어 {1,2,3,4,5} 에서 2가 있는지 탐색하고자 한다면, 중간값 3 > 2 이므로 3보다 큰 범위는 제외하고 작은 범위만을 살려놓는 것이다. {1,2} 만 남았다. 여기서 중간값은 (1+2)/2 =1 이고 1<2이다. 따라서 중간값보다 큰 범위인 {2}만 남게 된다.

이 과정을 binary함수로 직접 만들어 문제 해결에 활용할 수 있다.

[풀이]

cf ) medium을 while문 안에 작성해야, first와 last 값이 달라짐에 따라 중간값이 계속 업데이트 된다.