使用标准C/C++,帮我写一个折半查找算法。散200分
使用标准C/C++,帮我写一个折半查找算法。具体要求：
1。使用STL库，使用VECTORT
2。排序使用STL:sort(mVECTORT.begin(),mVECTORT.end(),函数)
3。最好支持模块类。
[解决办法]
先占坑
[解决办法]
template <class T, class V = _STD vector <T> , class P = struct comp_pred_elel>
struct SearchBinary
{
///
static inline intsearch ( const V& a, int v, int l, int r )
{
while ( r > = l )
{
int m = ( l + r ) / 2;
if ( P::pred ( v, a[l], a[r] ) )
return m;
if ( v < a[m] )
r = m - 1;
else
l = m + 1;
}
return -1;
}
};
[解决办法]
回去给你调试以下
[解决办法]
template <class T = int, class P = comp_pred_eq, class V = _STD vector <T > >
class ListUtils
{
public:
/// Linear search; Return the index of the element with value v; -1 if not found.
static inline intsearchLinear ( const V& a, int v, int l, int r )
{
for ( int i = l; i <= r; i++ )
{
if ( P::pred ( v, a[i], a[i+1] ) )
return i;
}
return -1;
}
/// Linear search; Return the index of the element with value v; -1 if not found.
static inline intsearchLinear1 ( const V& a, int v, int l, int r )
{
int idx = searchLinear ( a, v, l, r );
if ( idx != -1 )
return idx;
if ( v <= a[l] )
return l-1;
if ( v > = a[r] )
return r;
return -1;
}
/// Binary search; Return the index of the element with value v; -1 if not found.
static inline intsearchBinary ( const V& a, int v, int l, int r )
{
if ( l == r )
return -1;
while ( r > = l )
{
int m = ( l + r ) / 2;
if ( P::pred ( v, a[m], a[m+1] ) )
return m;
if ( v < a[m] )
r = m - 1;
else
l = m + 1;
}
return -1;
}
///
static inline intsearchBinary1( const V& a, int v, int l, int r )
{
int idx = searchBinary ( a, v, l, r );
if ( idx != -1 )
return idx;
if ( v <= a[l] )
return l;
if ( v > = a[r] )
return r;
return -1;
}
/// Linear interval search; Return the index of the first interval whose right value is greater than v.
static inline intsearchLinearInterval ( const V& a, int v, int l, int r )
{
for ( int i = l; i <= r; i++ )
{
if ( v < a[i] )
return i-1;
}
return i-1;
}
};
[解决办法]
google
[解决办法]
///////////////////////////////////程序实现///////////////////////////////////////////
//第一个版本的递归实现（binary_search_v1_recursion）
template <class Record, class Key>
int binary_search( Record * r, const int & low, const int & high, const Key & k )
{
int mid = ( low + high ) / 2;
if( low <= high )
{
if( r[mid] == k )
return mid;
else if( r[mid] < k )
return binary_search( r, mid+1, high, k );
else
return binary_search( r, low, mid-1, k );
}
else
return -1;
}
//第一个版本的迭代实现（binary_search_v1_iteration）
template <class Record, class Key>
int binary_search( Record * r, const int & size, const Key & k )
{
int low=0, high=size-1, mid;
while( low <= high )
{
mid = (low + high)/2;
if( r[mid] == k )
return mid;
else if( r[mid] < k )
low = mid + 1;
else
high = mid -1;
}
return -1;
}
[解决办法]
template <class Record, class Key>
int binary_search( Record * r, const int & low, const int & high, const Key & k )
{
int mid = (low + high)/2;
if( low < high )
{
if( k <= r[mid] )
binary_search( r, low, mid, k );
else
binary_search( r, mid+1, high, k );
}
else if( low == high )
{
if( k == r[mid] )
return low;
else
return -1;
}
else
return -1;
}
//第二个版本的迭代实现（binary_search_v2_iteration）
template <typename Record, typename Key>
int binary_search( Record * r, const int & size, const Key & k )
{
int low=0, high=size-1, mid;
while( low < high )
{
mid = (low + high) / 2;
if( k > r[mid] )
low = mid + 1;
else
high = mid;
}
if( low > high )
return -1;
else
{
if( k == r[low] )
return low;
else
return -1;
}
}
[解决办法]
关注。
[解决办法]
http://www.sogou.com/
www.baidu.com
[解决办法]
下面是标准STL Algorithm的实现
// TEMPLATE FUNCTION binary_search
template <class _FwdIt,
class _Ty> inline
bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
{// test if _Val equivalent to some element, using operator <
_First = std::lower_bound(_First, _Last, _Val);
return (_First != _Last && !(_Val < *_First));
}
// TEMPLATE FUNCTION binary_search WITH PRED
template <class _FwdIt,
class _Ty,
class _Pr> inline
bool binary_search(_FwdIt _First, _FwdIt _Last,
const _Ty& _Val, _Pr _Pred)
{// test if _Val equivalent to some element, using _Pred
_First = std::lower_bound(_First, _Last, _Val, _Pred);
return (_First != _Last && !_Pred(_Val, *_First));
}
[解决办法]
worddate 是个结构
v_42360 是个vector
lower_bound(); 是#include <algorithm>
if(find(v_42360.begin(), v_42360.end(), worddate) != v_42360.end())
{
worddate.wordnum = lower_bound(v_42360.begin(), v_42360.end(), worddate) - v_42360.begin();
worddate = v_42360.at(worddate.wordnum);
}loun
[解决办法]
来抢这两百分
嘿嘿
大家都回家吧
[解决办法]
全被huzhangyou给抢了,分点给偶什
vector <int> data(20);
iota(data.begin(), data.end(), 5); //生成5,6,7,...
random_shuffle(data.begin(), data.end()); // 打乱次序
sort(data.begin(),data.end()); //排序
vector <int> ::iterator p=lower_bound(data.begin(),data.end(),10); //二分查找,p指向 <=10的位置上.
自己实现的话,嗯~~,还是抄lower_bound把,呵呵
[解决办法]
C++ 标准库本身就提供 binary_search 函数,并且是支持模板的
[解决办法]
比较函数是自定义传入的
大 返回 1
等于 返回 0
小于 返回 -1
[解决办法]
挖坑~~~~
