两种查找模板

目录

1.顺序查找

2.折半查找（二分查找）

1.顺序查找

顺序查找是一种最简单、最基本的查找方法。其基本思想是：从数组的首元素开始，将元素逐个与待查找的关键字进行比较，直到找到相等的为止。若整个数组中没有与待查找关键字相等的元素，则查找不成功。

//顺序查找函数模板
//用顺序查找在数组 list 中查找值为 key 的元素
//若找到，返回该元素下标，否则返回-1
template <class T>
int seqSearch(const T list[], int n, const T& key)
{
	for (int i = 0; i < n; i++)
	{
		if (list[i] == key)
		{
			return i;
		}
	}
	return -1;    //搜索完未找到 返回-1
}

2.折半查找（二分查找）

折半查找也叫二分查找。它的时间复杂度是 O(log n)，而直接顺序查找的复杂度为O(n)。折半查找的条件是数组必须是有序的，折半查找方法的基本思想是：对于已按关键字排序的序列，经过一次比较后，可将序列纷割成两部分,然后只在有可能包含待查元素的一部分中继续

查找，并根据试探结果继续分割,逐步缩小查找范围，直至找到或找不到为止。

//折半查找函数模板
template <class T>
int binSearch(const T list[], int n, const T& key)
{
	int low = 1, high = n;;
	while (low <= high)    //low <= high 表示整个数组尚未查找完
	{ 
		int mid = low + (high - low) / 2;    //求中间元素下标，防止爆int
		if (key == list[mid])
			return mid;           //若找到，返回下标
		else if (key < list[mid])
			high = mid - 1;      
		else 
			low = mid + 1;       //否则将查找范围缩小到数组的后一半
	}
	return -1;        //没有找到返回-1
}

 接下来在模板中加入count变量记录查找的次数，观察两种查找的差异

#include<iostream>
using namespace std;

int count1 = 0, count2 = 0;
//顺序查找函数模板
//用顺序查找在数组 list 中查找值为 key 的元素
//若找到，返回该元素下标，否则返回-1
template <class T>
int seqSearch(const T list[], int n, const T& key)
{
	for (int i = 0; i < n; i++)
	{
		count1++;
		if (list[i] == key)
		{
			return i;
		}
	}
	return -1;    //搜索完未找到 返回-1
}

//折半查找函数模板
template <class T>
int binSearch(const T list[], int n, const T& key)
{
	int low = 1, high = n;;
	while (low <= high)    //low <= high 表示整个数组尚未查找完
	{ 
		count2++;
		int mid = low + (high - low) / 2;    //求中间元素下标，防止爆int
		if (key == list[mid])
			return mid;           //若找到，返回下标
		else if (key < list[mid])
			high = mid - 1;      
		else 
			low = mid + 1;       //否则将查找范围缩小到数组的后一半
	}
	return -1;        //没有找到返回-1
}

int main()
{
	int datal[] = { 1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20 };
	int pos1 = seqSearch(datal, 20, 8);
	cout << "seqSearch::position = " << pos1 << "  count=" << count1 << endl;
	int pos2 = binSearch(datal, 20, 8);
	cout << "binSearch::position = " << pos2 << "  count=" << count2 << endl;
	return 0;
}

 可见，二分查找比顺序查找时间复杂度要快很多。因此务必要掌握这种算法，对以后算法学习很重要。