[Day18]程序菜鸟自学C++资料结构演算法 – 线性搜寻法(Linear Search)与二分搜寻法(Half-Interval Search)

前言：资料结构的部分已经到了尾声，今天就要开始初探演算法的搜寻了！间天介绍的这两个搜寻法都是始於入门款，现在就来看看吧！

搜寻的概念：

在数据集合中寻找满足某种条件的数据元素。

平均搜寻长度(Average Search Length)
• 搜寻就是不断将数据元素的关键字与待查找关键字进行比
较，搜寻法在成功时平均比较的次数称作平均搜寻长度

• Pi：搜寻第i个数据元素的机率
• Ci：搜寻该元素的过程中比较的次数

线性搜寻法：

又称为循序搜寻法(Sequential Search)，这种演算法是最简单的，从第一笔资料到最後一笔资料进行比对，直到找到想找的资料就行。举个简单的例子：在书店买书的时候，若不是像漫画小说一样有集数的话，是不是都要一本一本扫过去才能找到像要的书？

图片来源：https://meet.eslite.com/Content/Images/Article/cats_20190214134118.jpg
这样就是线性搜寻喔！只不过资料量少还可以，资料量多就越没有效率了。

接着来实际实作看看

可以看到第一个搜寻的52有成功并标示出下标(82的下标为0)，而第二个搜寻的29则显示失败。

二分搜寻法：

又称为二元搜寻法(Binary Search)，通常用在已经整理好(有序数组)的资料，会先把资料分成前半部和後半部，如果想要找的资料在前半部，则在把前半部分分成两半，直到找到资料为止，这种搜寻法适合用在没有增删的静态资料。
P.S.如果资料量为基数，则会无条件进位。

实际时做看看就明白怎麽操作的了。

同样可以输出结果。

接着来比较看看两个搜寻法查找的次数


这样就明显的必较出了着的差异了。

最後再来分析两个演算法的时间复杂度。(描述演算法的执行时间，时间复杂度越低代表效率越好) P.S.假设资料皆为n笔。

线性搜寻法：
	最坏情况：找到最後一笔才找资料，时间复杂度为O(n)。

    最好情况：第一笔刚好就是想找的资料，时间复杂度为O(1)。
    
二元搜寻法：
	最坏情况：每次找资料都切半，需要网前半部或後半部找，时间复杂度为O(log n)。

    最好情况：第一次切半的中间值刚好就是想找的资料，时间资料的复杂度为O(1)。

本日小结：今天介绍完了两个基本的搜寻法，其他还有内插和费式同样也是常见的搜寻法，不过碍於篇幅可能无法介绍到，有兴趣的人可以到网路上找找相关资料，几乎都有很详细的解说喔o(^∀^)o

线性搜寻法

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

template<typename T, typename keyT, typename Function>
int linear_search(const vector <T>&vec,keyT key,Function fun) { //设立待搜寻的资料、关键字、条件的函数
	for (int i = 0; i < vec.size(); i++)
		if (fun(vec[i], key)) return i; //待搜寻的资料与关键字是否一样
	return -1; //表示搜寻失败
}
template<typename T, typename keyT>
bool Equal(T value,keyT key) { //建立比较函示判断资料与关键字是否一致
	return value == key;
}

int main() {
	vector<int> v{ 82,33,64,8,19,26,52 }; 
	int ret = linear_search(v, 52, Equal<int, int>); //传入线性表v,待搜寻的元素,比较函式及参数类型
	if (ret >= 0)std::cout << "搜寻的关键字：" << 52 << " 位置下标：" << ret << endl;
	ret = linear_search(v, 29, Equal<int, int>);
	if (ret >= 0)std::cout << "搜寻的关键字：" << 29 << " 位置下标：" << ret << endl;
	else std::cout << "搜寻失败\n";
	return 0;
}

二元搜寻法

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

int C = 0; //计算搜寻自数次数
template<typename T, typename keyT, typename Function>
int linear_search(const vector <T>& vec, keyT key, Function fun) { //设立待搜寻的资料、关键字、条件的函数
	for (int i = 0; i < vec.size(); i++)
		if (fun(vec[i], key)) return i; //待搜寻的资料与关键字是否一样
	return -1; //表示搜寻失败
}
template<typename T, typename keyT>
bool Equal(T value, keyT key) { //建立比较函示判断资料与关键字是否一致
	C++;
	return value == key;
}

template<typename T, typename keyT, typename Function>
int binary_search(const vector <T>& vec, keyT key, Function fun) {
	int low = 0; int high = vec.size() - 1; //定义第一个元素和最後一个元素的下标位置
	while (low <= high) { //表示存在此区间
		auto mid = (low + high) / 2;
		auto ret= fun(key,vec[mid]);
		if (ret == 0)return mid;
		else if (ret <= 0) { //说明关键字小於待搜寻元素
			high = mid - 1; //须更改下标
		}
		else {
			low = mid + 1;
		}
	}
	return -1;
}
template<typename T, typename keyT>
int Compare(keyT key,T value) { //同样建立比较函式
	C++;
	return key-value;
}
int main() {
	vector<int> v{ 82,33,64,8,19,26,52 };
	C = 0;
	int ret = binary_search(v, 26, Compare<int, int>); 
	if (ret >= 0)std::cout << "搜寻的关键字：" << 26 << " 位置下标：" << ret << endl;
	else std::cout << "搜寻失败\n";
	std::cout << "二分法比较次数：" << C << std::endl;

	C = 0;
	ret = linear_search(v, 26, Equal<int, int>);
	std::cout << "线性法比较次数：" << C << std::endl;
	
	return 0;
}