Question

关于C++中的2分搜索算法 请教高手

#include <iostream>
int a[100];
using namespace std;
template <class Type>
int binarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right)
{
int middle=(left+right)/2;
if(x==a[middle])
return middle;
if(x>a[middle])
left=middle+1;
else
right=middle-1;
}
return -1;
}

void main()
{
int n,x,m;
cout<<"请输入您要查找的数组长度：（最大长度为100）"<<endl;
cin>>n;
cout<<"请输入一个升序数组：（长度为"<<n<<"）"<<endl;
for(int count=0;count<n;count++)
cin>>a[count];
cout<<"请输入您要查询的数值："<<endl;
cin>>x;
int r=binarySearch(a,x,n);
if(r!=-1)
cout<<"该数下标："<<r<<endl;
else
cout<<"该数不在数组中!"<<endl;
cin>>m;
}

以上代码完成有序排列的2分搜索 但是如排列中出现多个相同关键字时则不是全部返回 请高手指点能输出相同关键字所有位置的2分搜索算法
例如:数组{1,1,1,2,2,2,3,3,3}查询2时能输出下标3,4,5
可改算法 也可改入口
都回答很不错 谢谢各位帮助
有没有办法在binarysearch中加个数组来实现呢
比如 bs(Type a[],const Type& x,int n,Type b[])
感谢各位 提高悬赏50

Answer 1

这个是利用STL的算法来实现的：

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

template <class T>
pair<T*, T*> BinarySearch(T *beg, T *end, T val)
{
return make_pair(lower_bound(beg, end, val), upper_bound(beg, end, val));
}

int main()
{
int a[] = {1,1,1,2,2,2,3,3,3};
int *beg = a;
int *end = a + sizeof a/sizeof a[0];

int numSearch = 2;
pair<int*, int*> range(BinarySearch(beg, end, numSearch));

if(range.first != end)
{
cout << "There are " << range.second - range.first << " elements found that are equal to " << numSearch;
cout << "\nTheir index are: ";
while(range.first != range.second)
{
cout << range.first++ - beg << ' ';
}
}
}

我自己也写了一个实现，需要算法做参考的话可以看看：

#include <iostream>
#include <utility>
using namespace std;

template <class T>
T* BinarySearchBase(T *beg, T *end, T val)
{
T *mid = beg + (end - beg)/2;
if(beg == end) return beg;
if(val == *mid) return mid;
if(val < *mid) return BinarySearchBase(beg, mid, val);
else return BinarySearchBase(mid+1, end, val);
}

template <class T>
pair<int, int> BinarySearch(T* beg, T* end, T val)
{
T *pos = BinarySearchBase(beg, end, val);

if(pos != end)
{
int *upper = pos;
int *lower = pos;

while(*upper == *pos)--upper;
while(*lower == *pos)++lower;

return make_pair(upper-beg+1, lower-beg-1);
}

return make_pair(end-beg, end-beg);
}

int main()
{
int a[] = {1,2,3,3,3,3,4,5,6};

pair<int, int> range(BinarySearch(a, a + sizeof a/ sizeof a[0], 3));
cout << "Found value 3 in range from index " << range.first << " to index " << range.second << endl;
}

用另外一个数组来存储下标显得太笨拙了，首先你不能确定要查找的数组中连续的元素有多少个，是否大于这个要存储的数组的宽度；另外二分查找法一般用于已排序好的数组，只要确定要查找的数(如果有多个)的首个下标和最后一个下标就可以了。这就是我上面代码的实现。

如果你非要用数组来存储下标的话用vector也可以解决，但不是最佳解决方案，原因如上所述。

Answer 2

#include <iostream>
int a[100];
using namespace std;
template <class Type>
bool binarySearch( Type a[], const Type& x, int n, int& begin, int& end )
{
int left = 0;
int right = n - 1;
while ( left <= right )
{
int middle = ( left + right ) / 2;
if ( x == a[middle] )
{
begin = end = middle;
while ( begin != 0 && a[begin - 1] == x )
{
begin--;
}
while ( end != n && a[end + 1] == x )
{
end++;
}
return true;
}
if ( x > a[middle] )
{
left = middle + 1;
}
else
{
right = middle - 1;
}
}
begin = end = -1;
return false;
}

void main()
{
int n, x, m;
cout << "请输入您要查找的数组长度：（最大长度为100）" << endl;
cin >> n;
cout << "请输入一个升序数组：（长度为" << n << "）" << endl;
for ( int count = 0; count < n; count++ )
{
cin >> a[count];
}
cout << "请输入您要查询的数值：" << endl;
cin >> x;

int begin, end;
bool isFind =binarySearch( a, x, n, begin, end );
if (isFind )
{
cout << "该数下标从 " << begin << " 到 " << end << " ." << endl;
}
else
{
cout << "该数不在数组中!" << endl;
}
cin >> m;
}

Answer 3

得到r之后对其前后单元进行测试就行了

可以啊，在
int middle=(left+right)/2;
if(x==a[middle])
{
这里对其前后单元进行测试，并将结果存到数组里面就行了
不过，返回参数最好改一下，改成数组b的元素个数
return middle;
}

Answer 4

增加一个函数，总体思路是既然你输入的是升序数组，那么相同的肯定在附近。只需要在你找的r附近小范围搜索就可以了。

void ReSearch(Type a[], int n, int r)
{
int i;
for(i=r;i<n;i++)
{
if(a[i]==a[r])
cout<<"下标："<<i<<endl;
else
break;
}
for(i=r-1;i>=0;i--)
{
if(a[i]==a[r])
cout<<"下标："<<i<<endl;
else
break;
}
}

全部代码如下：
#include <iostream>
int a[100];
using namespace std;
template <class Type>
int binarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right)
{
int middle=(left+right)/2;
if(x==a[middle])
return middle;
if(x>a[middle])
left=middle+1;
else
right=middle-1;
}
return -1;
}

void main()
{
int n,x,m;
cout<<"请输入您要查找的数组长度：（最大长度为100）"<<endl;
cin>>n;
cout<<"请输入一个升序数组：（长度为"<<n<<"）"<<endl;
for(int count=0;count<n;count++)
cin>>a[count];
cout<<"请输入您要查询的数值："<<endl;
cin>>x;
int r=binarySearch(a,x,n);
if(r!=-1)
ReSearch(a,n,r);
else
cout<<"该数不在数组中!"<<endl;
cin>>m;
}

Answer 5

我完全不懂