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

1、顺序查找

int sequenceSearch(int* arr, int size, int n) {	if (!arr || size<1){		return -1;	}	for (int i=0; i!=size; ++i){		if (n = arr[i]){			return i;		}	}	return -1;}

2、二分查找-非递归

int binarySearch(int* arr, int size, int n) {	if (!arr || size<1){		return -1;	}	int left, mid, right;	left = 0;	right = size - 1;	while (left <= right)	{		mid = (right + left) / 2;		if (n == arr[mid]) {			return mid;		}		else if (n > arr[mid]) {			left = mid + 1;		}		else {			right = mid - 1;		}	}	return -1;}

二分查找-递归

int binarySearch(int* arr, int n, int left, int right) {	if (!arr || left>right){		return -1;	}	int mid = /*(right + left) / 2*/left + (right - left) / 2;	if (n == arr[mid]){		return mid;	}		if (n > arr[mid]){		return binarySearch(arr, n, mid + 1, right);	}	if (n < arr[mid]) {		return binarySearch(arr, n, left, mid - 1);	}}

3、插值查找 - 基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。  

int InsertionSearch(int* arr, int n, int left, int right){	if (!arr || left > right) {		return -1;	}	//int mid = left + (right - left) / 2;	int mid = left + (n - arr[left]) / (arr[right] - arr[left])*(right - left);	if (arr[mid] == n)		return mid;	if (arr[mid] > n)		return InsertionSearch(arr, n, left, mid - 1);	if (arr[mid] < n)		return InsertionSearch(arr, n, mid + 1, right);}

 4、斐波那契查找

include 
   
    const int max_size = 20;//斐波那契数组的长度/*构造一个斐波那契数组*/void Fibonacci(int * F){	F[0] = 1;	F[1] = 1;	for (int i = 2; i < max_size; ++i)		F[i] = F[i - 1] + F[i - 2];}/*定义斐波那契查找法*/int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字{	int low = 0;	int high = n - 1;	int F[max_size];	Fibonacci(F);//构造一个斐波那契数组F 	int k = 0;	while (n > F[k] - 1)//计算n位于斐波那契数列的位置		++k;	//将数组a扩展到F[k]-1的长度	int* temp = new int[F[k] - 1];	memcpy(temp, a, n * sizeof(int));	for (int i = n; i < F[k] - 1; ++i)		temp[i] = a[n - 1];	/*	开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种　　1）相等，mid位置的元素即为所求　　2）>，low=mid+1,k-=2;　　说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，  k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，  所以可以递归的应用斐波那契查找。　　3）<，high=mid-1,k-=1。　　说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，  k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，  所以可以递归 的应用斐波那契查找。	*/	while (low <= high)	{		int mid = low + F[k - 1] - 1;		if (key < temp[mid])		{			high = mid - 1;			k -= 1;		}		else if (key > temp[mid])		{			low = mid + 1;			k -= 2;		}		else		{			if (mid < n)				return mid; //若相等则说明mid即为查找到的位置			else				return n - 1; //若mid>=n则说明是扩展的数值,返回n-1		}	}	delete[] temp;	return -1;}
   

5、树表查找- 二叉排序树/二叉查找树（Binary Search Tree）、2-3查找树、红黑树

6、分块查找 -  分块查找又称索引顺序查找，它是顺序查找的一种改进方法 //算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"； //即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，

//算法流程： // 先选取各块中的最大关键字构成一个索引表 // 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。

7、哈希查找

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