부스트 : int 배열과 일부 특수 int 배열을 가지고 가장 가까운 것을 찾는 방법?

Question

그래서 340, 6401 1280과 같은 30 개의 정수를 정렬하지 않은 배열을 사용합니다. 나는 int x를 가지고 있는데 이것은 사용자에 의해 만들어졌다. 배열의 어느 값이 해당 x 값에 가장 가까운 (더 낮은, 더 작은, 적은) 값인지를 찾아야합니다. 그런 일을하는 방법?

Answer 1

사용자 지정 비교 연산자와 std::max_element()을 사용할 수

struct limited_cmp { 
    int limit; 
    limited_cmp(int a_limit) : limit(a_limit) { 
    } 
    bool operator()(int left, int right) const { 
     if (left <= limit && limit < right) { 
     return false; 
     } 
     return (left < right); 
    } 
}; 

int main() { 
    std::vector<int> numbers = ...; 
    std::cout << "nearest is " 
     << *std::max_element(numbers.begin(), numbers.end(), limited_cmp(5)) 
     << std::endl; 
} 

Answer 2

배열이 정렬되지 않고 하나의 쿼리 만 수행하는 경우 가장 빠른 방법은 전체 배열을 스캔하는 것입니다. 배열의 크기보다 점근 적으로 더 많은 쿼리를 수행하는 경우 배열을 먼저 정렬 한 다음 각 쿼리에 대해 이진 검색을 수행해야합니다.

Answer 3

배열이 모두 정렬되지 않은 int 배열 인 경우 배열을 통과하는 O (n)보다 더 잘할 수 없습니다. 배열을 미리 정렬하는 데 드는 비용을 지불하려는 경우 이진 검색을 사용하여 O (logn)에서이를 수행 할 수 있습니다.

나는 당신을 위해 이것을 할 것이다 어떤 후원 안에 어떤 산법이 있다고 생각하지 않는다.

Answer 4

배열을 정렬하거나 std::set을 사용하고 std::lower_bound을 확인하십시오.