/*
* Copyright 2008-2010 NVIDIA Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*! \file binary_search.h
* \brief Search for values in sorted ranges.
*/
#pragma once
#include <thrust/detail/config.h>
#include <thrust/pair.h>
namespace thrust
{
/*! \addtogroup algorithms
*/
/*! \addtogroup searching
* \ingroup algorithms
* \{
*/
/*! \addtogroup binary_search Binary Search
* \ingroup searching
* \{
*/
//////////////////////
// Scalar Functions //
//////////////////////
/*! \p lower_bound is a version of binary search: it attempts to find
* the element value in an ordered range <tt>[first, last)</tt>.
* Specifically, it returns the first position where value could be
* inserted without violating the ordering. This version of
* \p lower_bound uses <tt>operator<</tt> for comparison and returns
* the furthermost iterator \c i in <tt>[first, last)</tt> such that,
* for every iterator \c j in <tt>[first, i)</tt>, <tt>*j < value</tt>.
*
* \param first The beginning of the ordered sequence.
* \param last The end of the ordered sequence.
* \param value The value to be searched.
* \return The furthermost iterator \c i, such that <tt>*i < value</tt>.
*
* \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
* \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
*
* The following code snippet demonstrates how to use \p lower_bound
* to search for values in a ordered range.
*
* \code
* #include <thrust/binary_search.h>
* #include <thrust/device_vector.h>
* ...
* thrust::device_vector<int> input(5);
*
* input[0] = 0;
* input[1] = 2;
* input[2] = 5;
* input[3] = 7;
* input[4] = 8;
*
* thrust::lower_bound(input.begin(), input.end(), 0); // returns input.begin()
* thrust::lower_bound(input.begin(), input.end(), 1); // returns input.begin() + 1
* thrust::lower_bound(input.begin(), input.end(), 2); // returns input.begin() + 1
* thrust::lower_bound(input.begin(), input.end(), 3); // returns input.begin() + 2
* thrust::lower_bound(input.begin(), input.end(), 8); // returns input.begin() + 4
* thrust::lower_bound(input.begin(), input.end(), 9); // returns input.end()
* \endcode
*
* \see http://www.sgi.com/tech/stl/lower_bound.html
* \see \p upper_bound
* \see \p equal_range
* \see \p binary_search
*/
template <class ForwardIterator, class LessThanComparable>
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last,
const LessThanComparable& value);
/*! \p lower_bound is a version of binary search: it attempts to find
* the element value in an ordered range <tt>[first, last)</tt>.
* Specifically, it returns the first position where value could be
* inserted without violating the ordering. This version of
* \p lower_bound uses function object \c comp for comparison
* and returns the furthermost iterator \c i in <tt>[first, last)</tt>
* such that, for every iterator \c j in <tt>[first, i)</tt>,
* <tt>comp(*j, value)</tt> is \c true.
*
* \param first The beginning of the ordered sequence.
* \param last The end of the ordered sequence.
* \param value The value to be searched.
* \param comp The comparison operator.
* \return The furthermost iterator \c i, such that <tt>comp(*i, value)</tt> is \c true.
*
* \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
* \tparam T is comparable to \p ForwardIterator's \c value_type.
* \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
*
* The following code snippet demonstrates how to use \p lower_bound
* to search for values in a ordered range.
*
* \code
* #include <thrust/binary_search.h>
* #include <thrust/device_vector.h>
* #include <thrust/functional.h>
* ...
* thrust::device_vector<int> input(5);
*
* input[0] = 0;
* input[1] = 2;
* input[2] = 5;
* input[3] = 7;
* input[4] = 8;
*
* thrust::lower_bound(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin()
* thrust::lower_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
* thrust::lower_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 1
* thrust::lower_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
* thrust::lower_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.begin() + 4
* thrust::lower_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()
* \endcode
*
* \see http://www.sgi.com/tech/stl/lower_bound.html
* \see \p upper_bound
* \see \p equal_range
* \see \p binary_search
*/
template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value,
StrictWeakOrdering comp);
/*! \p upper_bound is a version of binary search: it attempts to find
* the element value in an ordered range <tt>[first, last)</tt>.
* Specifically, it returns the last position where value could be
* inserted without violating the ordering. This version of
* \p upper_bound uses <tt>operator<</tt> for comparison and returns
* the furthermost iterator \c i in <tt>[first, last)</tt> such that,
* for every iterator \c j in <tt>[first, i)</tt>, <tt>value < *j</tt>
* is \c false.
*
* \param first The beginning of the ordered sequence.
* \param last The end of the ordered sequence.
* \param value The value to be searched.
* \return The furthermost iterator \c i, such that <tt>value < *i</tt> is \c false.
*
* \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
* \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
*
* The following code snippet demonstrates how to use \p upper_bound
* to search for values in a ordered range.
*
* \code
* #include <thrust/binary_search.h>
* #include <thrust/device_vector.h>
* ...
* thrust::device_vector<int> input(5);
*
* input[0] = 0;
* input[1] = 2;
* input[2] = 5;
* input[3] = 7;
* input[4] = 8;
*
* thrust::upper_bound(input.begin(), input.end(), 0); // returns input.begin() + 1
* thrust::upper_bound(input.begin(), input.end(), 1); // returns input.begin() + 1
* thrust::upper_bound(input.begin(), input.end(), 2); // returns input.begin() + 2
* thrust::upper_bound(input.begin(), input.end(), 3); // returns input.begin() + 2
* thrust::upper_bound(input.begin(), input.end(), 8); // returns input.end()
* thrust::upper_bound(input.begin(), input.end(), 9); // returns input.end()
* \endcode
*
* \see http://www.sgi.com/tech/stl/upper_bound.html
* \see \p lower_bound
* \see \p equal_range
* \see \p binary_search
*/
template <class ForwardIterator, class LessThanComparable>
ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last,
const LessThanComparable& value);
/*! \p upper_bound is a version of b
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
Thrust v1.2是个CUDA并行算法库,含有一个类似于C++标准模板库(STL)的界面。Thrust提供了一个灵活的高级GPU编程接口,可以极大地增强开放者的生产力,可以利用Thrust迅速开发高性能的应用程序。这是一个非常重要的第三方CUDA开发库。 Thrust is a CUDA library of parallel algorithms with an interface resembling the C++ Standard Template Library (STL). Thrust provides a flexible high-level interface for GPU programming that greatly enhances developer productivity. Develop high-performance applications rapidly with Thrust!
资源推荐
资源详情
资源评论
收起资源包目录
Thrust v1.2 CUDA并行算法库 (348个子文件)
CHANGELOG 8KB
binary_search.h 37KB
functional.h 30KB
device_reference.h 27KB
segmented_scan.h 25KB
unique.h 20KB
vector_base.h 19KB
sort.h 18KB
reduce.h 17KB
tuple.h 17KB
remove.h 17KB
type_traits.h 15KB
gather.h 15KB
iterator_facade.h 14KB
replace.h 13KB
transform.h 13KB
partition.h 12KB
scan.h 12KB
device_ptr.h 12KB
zip_iterator_base.h 12KB
copy.h 12KB
extrema.h 11KB
linear_congruential_engine.h 9KB
uniform_real_distribution.h 9KB
uniform_int_distribution.h 9KB
xor_combine_engine.h 9KB
normal_distribution.h 9KB
pair.h 9KB
copy_cross_space.h 9KB
subtract_with_carry_engine.h 8KB
discard_block_engine.h 8KB
tuple_transform.h 8KB
iterator_categories.h 8KB
xor_combine_engine_max.h 8KB
scatter.h 8KB
merging_sort.h 8KB
constant_iterator.h 8KB
linear_feedback_shift_engine.h 7KB
tuple_meta_transform.h 7KB
binary_search.h 7KB
scatter.h 7KB
transform_iterator.h 7KB
transform_scan.h 7KB
dereference.h 7KB
zip_iterator.h 7KB
counting_iterator.h 7KB
reverse_iterator.h 7KB
permutation_iterator.h 7KB
transform.h 6KB
pinned_allocator.h 6KB
sequence.h 6KB
inner_product.h 6KB
unique.h 5KB
iterator_category_to_traversal.h 5KB
copy.h 5KB
host_vector.h 5KB
is_sorted.h 5KB
logical.h 5KB
segmented_scan.h 5KB
device_vector.h 5KB
set_intersection.h 5KB
raw_buffer.h 5KB
stable_radix_sort_bits.h 5KB
binary_search.h 5KB
partition.h 5KB
remove.h 5KB
adjacent_difference.h 4KB
config.h 4KB
equal.h 4KB
sort.h 4KB
count.h 4KB
reduce.h 4KB
copy_device_to_device.h 4KB
iterator_adaptor.h 4KB
merge_sort.h 4KB
transform_reduce.h 4KB
reduce.h 4KB
binary_search.h 4KB
odd_even_sort.h 4KB
arch.h 4KB
segmented_scan.h 4KB
uninitialized_copy.h 4KB
random.h 4KB
trivial_copy.h 4KB
device_new.h 4KB
unique.h 4KB
device_malloc_allocator.h 4KB
device_new_allocator.h 4KB
binary_search.h 3KB
scan.h 3KB
swap_ranges.h 3KB
extrema.h 3KB
copy.h 3KB
scan.h 3KB
copy.h 3KB
uninitialized_fill.h 3KB
scan.h 3KB
normal_iterator.h 3KB
stable_radix_sort_util.h 3KB
transform.h 3KB
共 348 条
- 1
- 2
- 3
- 4
资源评论
beyondht2003
- 粉丝: 2
- 资源: 7
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功