백준/JAVA
[JAVA] 백준_10815
영초_
2023. 8. 3. 00:39
[문제]
10815번: 숫자 카드
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
[알고리즘]
이분탐색을 이용하는 문제였다.
하나하나 다 확인해보는 선형탐색과는 달리, 이분탐색은 확인하려는 값이 중간값보다 큰지 작은지 확인하고 만약 크다면 / 작다면 중간값보다 작은 / 큰 값은 볼 필요가 없으므로 중간값보다 큰 / 작은 값만 놓고 이와같은 과정을 반복해서 탐색하는 방식이다.
예를 들어 {1,2,3,4,5} 에서 2가 있는지 탐색하고자 한다면, 중간값 3 > 2 이므로 3보다 큰 범위는 제외하고 작은 범위만을 살려놓는 것이다. {1,2} 만 남았다. 여기서 중간값은 (1+2)/2 =1 이고 1<2이다. 따라서 중간값보다 큰 범위인 {2}만 남게 된다.
이 과정을 binary함수로 직접 만들어 문제 해결에 활용할 수 있다.
[풀이]
cf ) medium을 while문 안에 작성해야, first와 last 값이 달라짐에 따라 중간값이 계속 업데이트 된다.
