Tutorial: 이진탐색(라이브러리 사용법) timer 1s memory 1024MB

이전 이진탐색 문제에서는 정렬된 데이터에서 특정 값을 찾는 알고리즘을 구현하였다.

이번 문제에서는 이진탐색을 직접 구현하지 않고, 이미 만들어진 함수 사용법을 익히는것이 목표이다.

[ C/C++ ]

C++에서는 이진탐색과 관련된 함수들로 binary_search, lower_bound, upper_bound라는 함수를 제공하나,

lower_bound만 알아도 이진탐색 문제 풀기에는 충분하다.

lower_bound 는 정렬된 데이터에서 찾을 값 이상이 들어있는 최초의 지점을 구해준다. (upper_bound는 찾을 값 초과가 들어있는 최초 지점)

lower_bound 사용법은 sort 함수와 유사하다.

std::lower_bound(배열의 시작 위치, 배열의 끝 위치의 다음 위치, 찾을 값)

반환값은 인덱스(상대적 위치)가 아니라 이터레이터(주소값, 절대적 위치)가 반환된다. 따라서 반환값에 시작 주소값을 빼주면 인덱스를 구할 수 있다. (찾지 못했으면 배열의 마지막 원소 다음 위치 반환)

아래 코드는 정렬된 데이터에서 target을 찾아 인덱스를 구하는 코드이다.

#include <stdio.h>
#include <algorithm>

int main(){
    int A[9] = {1,4,9,11,11,11,20,20,45};
    int target = 11;
    int idx = std::lower_bound(A+0, A+9, target) - A;
    printf("%d", idx); // 3 출력
    return 0;
}

[ Python ]

Python의 경우 C++의 lower_bound와 같은 기능을 사용하고 싶으면 bisect 라이브러리를 불러오면 된다.

bisect.bisect_left로 사용하며, 사용법은 아래 내용을 참고한다.

import bisect
A = [1,4,9,11,11,11,20,20,45]
target = 11
idx = bisect.bisect_left(A,target)
print(idx) # 3 출력

[ 문제 ]

N개의 정렬된 데이터가 주어지고 Q개의 질의값이 주어진다.

각 Q개의 질의값에 대해 가장 가까운 데이터 값을 출력하시오.

[ 주의사항 ]

입출력이 많은 문제임에 유의하라. (입출력에 의한 시간초과 주의!! 경우에 따라 입출력 최적화 코드가 필요할 수도 있다.)