本文共 2505 字，大约阅读时间需要 8 分钟。

一：简单顺序查找

考虑到顺序查找算法的特点，将数组中储存元素的下标范围规定为1~n，因此储存数组需要描述为A[n + 1]，在实现查找时，搜索方向可以从1到n，也可以从n到1，来为节省时间，一般采用后者，从n到1时，下标为0的 A[0]充当的角色为监视哨，A[0]存储需要查找的数，当查找失败时，肯定能在A[0]中找到该元素，这样可以通过返回下标0来表示查找失败。

#include
   
    using namespace std;	// 从左到右查找int searchl(int* a, int n){
   	for(int i = 1; i < 11; i++)	{
   	    if(a[i] == n)	        return i;			}	return -1;}// 从右到左查找int searchr(int* a, int n){
   	for(int i = 11; i > 0; i--)	{
   		if(a[i] == n)		    return i;	}	return -1;}// 从右到左查找+监视哨int searchp(int* a, int n){
   	int i = 10;	a[0] = n;	while(a[i] != n)	    i--;	return i;}int main(){
   	// 初始化条件 	int a[11];	for(int i = 1; i < 11; i++)	    a[i] = i;	int n1 = 6, n2 = -5;		// 从左到右查找	cout << searchl(a, n1) << endl;	cout << searchl(a, n2) << endl;		// 从右到左查找	cout << searchr(a, n1) << endl;	cout << searchr(a, n2) << endl;		// 从右到左查找+监视哨	cout << searchp(a, n1) << endl;	cout << searchp(a, n2) << endl;	 	return 0;}
   

查找方式为“从右到左查找+监视哨”的算法分析：

二：有序表的二分查找

如果表中的数据都是排列好的，那么就无需从头开始找，就像翻字典一样。

代码实现：

#include
   
    using namespace std;int binSearch_1(int* a, int n, int t){
   	int mid, low = 0, high = n - 1;	while(low <= high)	{
   		mid = (low + high) / 2;		if(t == a[mid])		    return mid;		if(t < a[mid])		    high = mid - 1;		else		    low = mid + 1;	}	return -1;}int binSearch_2(int* a, int t, int low, int high){
   	if(low > high)	    return -1;	else	{
   		int mid = (low + high) / 2;		if(a[mid] == t)		    return mid;		if(a[mid] < t)		    return binSearch_2(a, t, mid + 1, high);		else		    return binSearch_2(a, t, low, mid - 1);	}}int main(){
   	// 初始化题目条件	int a[10] = {
   2, 3, 9, 15, 30, 42, 47, 53, 86, 100};	int n = 10, t1 = 47, t2 = 11;		// 一般的二分查找	cout << binSearch_1(a, n, t1) << endl;	cout << binSearch_1(a, n, t2) << endl;		// 递归算法的二分查找	cout << binSearch_2(a, t1, 0, 9) << endl;	cout << binSearch_2(a, t2, 0, 9) << endl; 	return 0;}
   

递归算法的二分查找算法分析：

#include
   
    using namespace std;void binSearch(int* a, int low, int high, int len = 1) {
   	if (low > high)		return;	else	{
   		int t = 1;		int mid = (low + high) / 2;		if (len == 5)			cout << a[mid] << endl;		binSearch(a, mid + 1, high, len + 1);	    binSearch(a, low, mid - 1, len + 1);	}}int main(){
   	// 初始化题目条件	int a[19];	for (int i = 0; i < 19; i++)	    a[i] = i;	binSearch(a, 0, 18);	return 0;}
   

三：索引顺序表的查找

许多情况下可能遇到这样的表：整个表中未必有序，但若划分成若干块后，每一块中的所有元素均大于或小于其后面的所有元素，称这种特性为分块有序，因此可以为该顺序表建立一个索引表，索引表中为每一块设置设置一索引项，每一索引项包括两部分：该块的起始地址和该块中最大(或最小)关键字的值（或是所限定的最大（小）关键字）。将这些索引项按顺序排列成一有序表，即为索引表。

转载地址：http://dtnqi.baihongyu.com/