# 使用标准C/C++,帮小弟我写一个折半查找算法。散200分(2)

www.MyException.Cn  网友分享于：2013-02-15  浏览：13次

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
------解决方案--------------------

// 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
------解决方案--------------------

------解决方案--------------------

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的位置上.