【基础算法】顺序查找折半查找&C++实现-创新互联

●顺序查找

  顺序查找比较简单，就是顺序遍历我们所要查找的内容，判断并找出相应的目标数。比较简单，在这里不用图形说明程序实现具体情况。当面临大量数据时，顺序查找的效率非常低，时间复杂度大，所以会采用其他方法进行查找。

目前成都创新互联已为千余家的企业提供了网站建设、域名、网站空间、绵阳服务器托管、企业网站设计、邱县网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

#includeusing namespace std;
#define size 20
class shunxu {
public:
	void searchfun()
	{
		for (int i = 0; i< size; i++)
		{
			if (arr[i] == n)
				place = i;
		}
	}
	int arr[size];
	int n;
	int place;
};
void text()
{
	shunxu sx;
	cout<< "输入顺序查找的内容：";
	for (int i = 0; i< size; i++)
	{
		cin >>sx.arr[i];
	}
	cout<< "输入要查找的目标：";
	cin >>sx.n;
	sx.searchfun();
	cout<< "所查找目标的位置："<< sx.place<< endl;
}
int main()
{
	text();
}

---

●折半查找

  在下面我们从十个数中查找目标数，用折半查找法进行查找（在这里不进行排序，只进行折半查找），如下图所示。

第一次，low=0、high=9  => mid=4,进行判断arr[mid]

第二次，low=5、high=9  => mid=7,进行判断arr[mid]>n，则定位到前半段，high=mid-1;

第三次，low=5、high=6  => mid=5,进行判断arr[mid]

第四次，low=6、high=6  => mid=6,进行判断arr[mid]=n，找到目标值的位置，place=6；

当面临大量数据时，我们先将这些数据进行排序，再用折半查找法进行查找。这样可以极大的提高查找效率，降低时间复杂度从而快速的寻找到目标数。 

#includeusing namespace std;
#define size 20
class halfsearch {
public:
	void bullesort_1();  //对随机生成的数进行排序，随机找一种排序算法即可，这里用冒泡这种简单排序法
	int halfsearch_1()  //折半查找
	{
		int low=0, mid, high=size-1;
		while (low<=high)
		{
			mid = (low + high) / 2;     //折半
			if (arr[mid] == n)
				return place = mid;
			else if (arr[mid] >n)    //目标数在前一半里
				high = mid - 1;
			else                      //目标数在后一半里
				low = mid + 1;
		}
		return place = 0;
	}
	void showplace()
	{
		if (place == 0)
			cout<< "没有找到"<< endl;
		else
			cout<< "找到目标数且位置为："<< place+1<< endl;
	}
	int arr[size];
	int n;
	int place;
};
void halfsearch::bullesort_1()  //冒泡排序法
{
		int temp;
		for (int i = 0; i< size-1; i++)
		{
			for(int j=size-1;j>i;j--)
			{ 
				if (this->arr[j ]< this->arr[i])
				{
					temp = this->arr[j ];
					this->arr[j ] = this->arr[i];
					this->arr[i] = temp;
				}
			}
		}
}
void text()
{
	halfsearch hs;
	srand(time(NULL)); 
	for(int i=0;i>hs.n;   //输入要查找的目标数
	hs.halfsearch_1();   //进行折半查找
	hs.showplace();  //输出查找到的位置
}
int main()
{
	text();
}

---

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文标题：【基础算法】顺序查找折半查找&C++实现-创新互联
标题网址：http://cdkjz.cn/article/cssohi.html