二分搜索.cpp

算法分析与设计中的二分搜索算法代码

#include <iostream>
using namespace std;
#define N 7
class Jobtype
{
public:
	int key;
	int index;
public:
	void h(int v1,int v2)	
	{
		key=v1;
		index=v2;
	}
};
//排序
void Swap(Jobtype *a,int i,int j)
{
	Jobtype temp;
	temp=a[i];a[i]=a[j];a[j]=temp;	
}

int Partition(Jobtype *a,int p,int r)
{
	int i=p,j=r+1;
	Jobtype x;
	x=a[p];
	while(true)
	{
		while(a[++i].key<x.key);
		while(a[--j].key>x.key);
		if(i>=j)
			break;
		Swap(a,i,j);
	}	
	a[p]=a[j];
	a[j]=x;

	return j;
}

void QuickSort(Jobtype a[],int p,int r)
{
	if(p<r)
	{
		int q=Partition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}

}
//搜索x
int BinarySearch(Jobtype a[],int & x,int n)
{
	int left=1;
	int right=n;
	while(left<=right)
	{
		int middle=(left+right)/2;
		if(x==a[middle].key)
			return middle;
		if(x>a[middle].key)
			left=middle+1;
		else
			right=middle-1;
	}
	return -1;
}
void main()
{
	Jobtype *a=new Jobtype[N];
	int n,x,key;
	cout<<"输入数组长度：";
	cin>>n;
	cout<<endl<<"输入待搜索的值：";
	cin>>x;
	cout<<"输入数组元素值："<<endl;
	for(int i=1;i<=n;i++)
	{
		cout<<"a["<<i<<"]-->";
		cin>>key;
		a[i].h(key,i);
	}
//数组元素7,8,5,4,9,1
	QuickSort(a,1,n);
	int k;
	k=BinarySearch(a,x,n);
	if(k==-1)
		cout<<"没有x值。";
	else
	{
		cout<<"比待搜索值x小的最大值位置：";
		cout<<a[k-1].index<<endl;
		cout<<"比待搜索值x大的最小值位置：";
		cout<<a[k+1].index;
	}

	cout<<endl;
}