【基础算法】顺序查找 折半查找 & C++实现

●顺序查找

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

#include<iostream>
using 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]<n，则定位到后半段，low=mid+1;

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

第三次，low=5、high=6  =>  mid=5,进行判断arr[mid]<n，则定位到后半段，low=mid+1;

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

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

#include<iostream>
using 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<size;i++)
	{ 
		hs.arr[i] = rand() / 1000 + 100;   //生成100~200的随机数
	}
	hs.bullesort_1();	//先进行排序，后进行折半查找
	cout << "随机生成的数排序后如下：" << endl;
	for (int j = 0; j < size; j++)
	{
		cout << hs.arr[j] << " ";     
	}        
	cout<<endl;
	cout << "输入要查找的数：";
	cin >> hs.n;   //输入要查找的目标数
	hs.halfsearch_1();   //进行折半查找
	hs.showplace();  //输出查找到的位置
}
int main()
{
	text();
}