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

代码实现了五种方法对顺序表进行查找。

1、主要函数功能介绍：

// 顺序查找方法一：for循环遍历int Binary_Search(int *arr, const int n, const int key);// 顺序查找方法二： 设置“哨兵”位，优化边界判断比较int Sequential_Search(int *arr, const int n, const int key);// 折半查找一：常规思路int Sequential_Search2(int *arr, const int n, const int key);// 折半查找二：递归实现int Binary_Search2(int *arr, int low, int hight, const int key);// 斐波那契查找int Fibonacci_Search(int *arr, int n, int key);

2、程序运行结果：

Find key = 0#Sequential_Search: Find key at 0#Sequential_Search2: Find key at 0#Binary_Search: Find key at 0#Binary_Search2: Find key at 0#Fibonacci_Search: Find key at 0Find key = 15#Sequential_Search: Find key at 15#Sequential_Search2: Find key at 15#Binary_Search: Find key at 15#Binary_Search2: Find key at 15#Fibonacci_Search: Find key at 15Find key = 20#Sequential_Search: Not find key, return 0#Sequential_Search2: Not find key, return 0#Binary_Search: Not find key, return 0#Binary_Search2: Not find key, return 0#Fibonacci_Search: Not find key, return 0

3、完整代码程序

#include
   
    #include 
    
     using namespace std;int Binary_Search(int *arr, const int n, const int key);int Sequential_Search(int *arr, const int n, const int key);int Sequential_Search2(int *arr, const int n, const int key);int Binary_Search2(int *arr, int low, int hight, const int key);int Fibonacci_Search(int *arr, int n, int key);void main(){
   	int arr[50] = {
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17 };	cout << "Find key = 0\n";	cout << Sequential_Search(arr, 18, 0) << endl;	cout << Sequential_Search2(arr, 18, 0) << endl;	cout << Binary_Search(arr, 18, 0) << endl;	cout << Binary_Search2(arr, 0, 18, 0) << endl;	cout << Fibonacci_Search(arr, 18, 0) << endl;	cout << "\nFind key = 15\n";	cout << Sequential_Search(arr, 18, 15) << endl;	cout << Sequential_Search2(arr, 18, 15) << endl;	cout << Binary_Search(arr, 18, 15) << endl;	cout << Binary_Search2(arr, 0, 18, 15) << endl;	cout << Fibonacci_Search(arr, 18, 15) << endl;	cout << "\nFind key = 20\n";	cout << Sequential_Search(arr, 18, 20) << endl;	cout << Sequential_Search2(arr, 18, 20) << endl;	cout << Binary_Search(arr, 18, 20) << endl;	cout << Binary_Search2(arr, 0, 18, 20) << endl;	cout << Fibonacci_Search(arr, 18, 20) << endl;}int Sequential_Search(int *arr, const int n, const int key){
   	for (int i = 0; i < n; i++) {
   		if (arr[i] == key) {
   			cout << "#Sequential_Search: Find key at ";			return i;		}	}	cout << "#Sequential_Search: Not find key, return ";	return 0;}int Sequential_Search2(int *arr, const int n, const int key){
   	if (arr[0] == key) {
   		cout << "#Sequential_Search2: Find key at ";		return 0;	}	int temp = arr[0];	arr[0] = key;	int i = n;	while (arr[i] != key)		i--;	if (i != 0) {
   		arr[0] = temp;		cout << "#Sequential_Search2: Find key at ";		return i;	}	else	{
   		arr[0] = temp;		cout << "#Sequential_Search2: Not find key, return ";		return 0;	}}int Binary_Search(int *arr, const int n, const int key){
   	int low = 0, hight = n - 1, mid;	while (low <= hight)	{
   		// 折半查找		//mid = (low + hight) / 2;		// 插值查找		mid = low + (double(key - arr[low]) / double(arr[hight] - arr[low]))*(hight - low);		if (arr[mid] == key) {
   			cout << "#Binary_Search: Find key at ";			return mid;		}		else if (key < arr[mid])			hight = mid - 1;		else			low = mid + 1;	}	cout << "#Binary_Search: Not find key, return ";	return 0;}int Binary_Search2(int *arr, int low, int hight, const int key){
   	int mid = (low + hight) / 2;	if (arr[mid] == key) {
   		cout << "#Binary_Search2: Find key at ";		return mid;	}	else if (low > hight) {
   		cout << "#Binary_Search2: Not find key, return ";		return 0;	}	else if (key < arr[mid])		Binary_Search2(arr, low, mid - 1, key);	else		Binary_Search2(arr, mid + 1, hight, key);}int Fibonacci_Search(int *arr, int n, int key){
   	const int F[] = {
    0,1,1,2,3,5,8,13,21,34 };	int low, hight, mid, k;	low = 0; hight = n - 1; k = 0;	while (n > F[k] - 1)		k++;	for (int i = n; i < F[k]-1; i++)		arr[i] = arr[n - 1];	while (low <= hight)	{
   		mid = low + F[k - 1] - 1;		if (key < arr[mid]) {
   			hight = mid - 1;			k = k - 1;		}		else if (key > arr[mid]) {
   			low = mid + 1;			k = k - 2;		}		else		{
   			cout << "#Fibonacci_Search: Find key at ";			if (mid <= n - 1)				return mid;			else				return n - 1;		}	}	cout << "#Fibonacci_Search: Not find key, return ";	return 0;}
    
   

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