Tutorial: Binary Search (Library Usage) timer 1s memory 1024MB

In the previous Binary Search problem, we implemented an algorithm to find a specific value in sorted data.

In this problem, the goal is to learn how to use pre-built functions instead of implementing binary search directly.

[ C/C++ ]

In C++, functions related to binary search such as binary_search, lower_bound, and upper_bound are provided,

but knowing only lower_bound is sufficient for solving binary search problems.

lower_bound finds the first position in sorted data that contains a value greater than or equal to the target value. (upper_bound is the first position containing a value strictly greater than the target value)

The usage of lower_bound is similar to the sort function.

std::lower_bound(start position of array, position after the end of array, value to find)

The return value is not an index (relative position) but an iterator (address, absolute position). Therefore, you can obtain the index by subtracting the starting address from the return value. (If not found, it returns the position after the last element of the array)

The code below finds the target in sorted data and calculates the index.

#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); // Outputs 3
    return 0;
}

[ Python ]

In the case of Python, if you want to use a function similar to C++'s lower_bound, you can import the bisect library.

It is used as bisect.bisect_left; refer to the content below for usage.

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

[ Problem ]

N sorted data points are given, and Q query values are provided.

For each of the Q query values, output the closest data value.

[ Precautions ]

Note that this problem involves a large amount of input and output. (Beware of time limits due to I/O!! In some cases, I/O optimization code may be necessary.)