查找算法

发表于 分类于

查找算法。

例程如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <string.h>

int LinearSearch(int a[], int length, int keyValue)
{
	// 线性查找，一般当序列无序时使用
	for(int i = 0; i < length; i++)
	{
		if(a[i] == keyValue)
			return i;
	}
	return -1;
}

int BinarySearch(int a[], int length, int keyValue)
{
	// 折半查找，适用于有序序列
	int L = 0;
	int R = length - 1;
	while(L <= R)
	{
		int M = (L+R)/2;
		if(a[M] > keyValue)
			R = M - 1;
		else if(a[M] < keyValue)
			L = M + 1;
		else
			return M;
	}
	return -1;
}

int OMGSearch(int a[], int length, int keyValue)
{
	// 插值查找，适用于元素分布均匀的有序序列，因其按照线性比例来确定M值
	int L = 0;
	int R = length - 1;
	while(L <= R)
	{
		// M值根据如下数学方程获得：
		// (keyValue - a[L]) : (M - L) = (a[R] - a[L]) : (R - L)
		int M = (keyValue - a[L]) * (R - L) / (a[R] - a[L]) + L;
		if(a[M] > keyValue)
			R = M - 1;
		else if(a[M] < keyValue)
			L = M + 1;
		else
			return M;
	}
	return -1;
}

const int max_size = 20; // 斐波那契数组的长度 

void Fibonacci(int F[])  
{  
	// 构造一个斐波那契数组
	F[0] = 0;  
	F[1] = 1;  
	for(int i = 2; i < max_size; i++)  
		F[i] = F[i-1] + F[i-2];  
}

int FibonacciSearch(int a[], int length, int keyValue)
{
	// 斐波那契查找
	int L = 0;  
	int R = length - 1;  

	int F[max_size];  
	Fibonacci(F); // 构造一个斐波那契数组F   

	int k = 0;  
	while(length > F[k]) // 计算length位于斐波那契数列的位置  
		k++;

	int temp[F[k]-1]; // 将数组a扩展到F[k]-1的长度  
	memcpy(temp,a,length*sizeof(int));  

	for(int i = length; i < F[k]-1; i++)  
		temp[i] = a[length-1];  

	while(L <= R)  
	{  
		int M = L + F[k-1] - 1; //
		if(keyValue < temp[M])  
		{  
			R = M - 1;  
			k -= 1;  
		}  
		else if(keyValue > temp[M])  
		{  
			L = M + 1;  
			k -= 2;  
		}  
		else  
		{  
			if(M < length)  
				return M; // 若相等则说明M即为查找到的位置  
			else  
				return length-1; // 若M>=length则说明是扩展的数值,返回length-1  
		}  
	}    
	return -1;
}

void main()
{
	int a[] = {0,1,2,3,4,5,6,7,8,9,10,15,20,25,30,40,50,70,100};
	int length = sizeof(a)/sizeof(int);
	int keyValue = 25;
	printf("LinearSearch Result: %d at %d\n",keyValue,LinearSearch(a,length,keyValue));
	printf("BinarySearch Result: %d at %d\n",keyValue,BinarySearch(a,length,keyValue));
	printf("OMGSearch Result: %d at %d\n",keyValue,OMGSearch(a,length,keyValue));
	printf("FibonacciSearch Result: %d at %d\n",keyValue,FibonacciSearch(a,length,keyValue));
}