배열에서 K번째 수

Time Limit: 5000 msMemory Limit: 256 MBGold V5Author: Super Admin이분 탐색

N개의 정수로 이루어진 배열에서 K번째로 작은 수를 구하라. N이 최대 5,000,000이므로 이분 탐색을 써서 효율적으로 구하라.

값 범위 [lo, hi]에서 mid를 잡고 mid 이하인 원소 수가 K 이상이면 hi=mid, 미만이면 lo=mid+1로 좁혀 나간다.

입력

첫째 줄에 N과 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000,000, 1 ≤ K ≤ N)

둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (-10^9 ≤ 각 수 ≤ 10^9)

K번째로 작은 수를 출력하라.

5 3
3 1 4 1 5

Problem Statistics

Total submissions

Accepted

83.3%

Acceptance rate

Unique solvers