目录
斐波那契查找
测试代码
# include "stdio.h"
#include "time.h"
#include "string.h"
#define maxsize 1000
#define length 100
void print(int*arr) {
printf("\n");
for (int i = 0; i < length; i++) {
printf("%d ", *(arr + i));
}
printf("\n");
}
/*--------------------------------------------------------非递归，归并排序----------------------------------*/
void insert(int *arr, int *tmp, int s, int m, int n) {
int j;
int k;
for (j = m, k = s; j < n&&s < m; k++) {
if (arr[s] <= arr[j])
tmp[k] = arr[s++];
else
tmp[k] = arr[j++];
}
while (j < n) {
tmp[k++] = arr[j++];
}
while (s < m) {
tmp[k++] = arr[s++];
}
}
void merge(int* arr, int*tmp, int k, int n) {
int j;
for (j = 0; j <= n - 2 * k; j += 2 * k) {
insert(arr, tmp, j, j + k, j + 2 * k);
}
if (j < n - k) {
insert(arr, tmp, j, j + k, n);
}
else {
while (j < n) {
tmp[j] = arr[j++];
}
}
}
void merge_sort(int* arr, int n) {
int k = 1;
int tmp[maxsize];
do {
merge(arr, tmp, k, n);
k *= 2;
merge(tmp, arr, k, n);
k *= 2;
} while (k < n);
}
/*-----------------------------二分查找--------------------------------------------------*/
//int search_bin(int* arr, int key, int n) {
// int min;
// int low = 0;
// int high = n;
// while (low <= high) {
// min = (low + high) / 2;
// if (key == arr[min])
// return min;
// if (arr[min] < key)
// low = min + 1;
// else
// high = min - 1;
//
// }
// return -1;
//}
int f[100] = { 0,1 };/*全局变量：斐波那契数列*/
/*----------------------------------------------算法主体-----------------*/
int Fibonacci_Search(int* arr, int n, int key) {
int mid;
int low = 0;
int high;/*数组下标从0开始*/
int k = 0;
while (n > f[k]) {/*找到k值*/
k++;
}
for (int i = n; i < f[k]; i++) {
arr[i] = arr[n - 1];
}
high = f[k] - 1;/*扩充后最后一个元素的下标*/
while (low <= high) {
mid = low + f[k - 1] - 1;
if (arr[mid] == key) {
if (mid <= n - 1)/*原表的下标*/
return mid;
else
return n - 1;/*匹配的是扩充的元素*/
}
if (arr[mid] < key) {
low = mid + 1;
k -= 2;/*f[k]=右半部分的长度*/
}
else {
high = mid-1;
k -= 1;/*f[k]=左半部分的长度*/
}
}
return -1;
}
/*--------------------------------------------------------------------*/
int main() {
int index;
int key;
srand(12);
int a[maxsize];
for (int i = 0; i < length; i++) {
a[i] = (int)(rand() % 100);
}
merge_sort(&a, length);
printf("查找表 \n");
for (int i = 0; i < length; i++) {
printf("$%2d:%2d ", i, a[i]);
if ((i + 1) % 10 == 0)
printf("\n");
}
//index = search_bin(a, 43, maxsize);
//printf("%d\n", index);
for (int i = 2; i < 100; i++) {/*初始化斐波那契数列*/
f[i] = f[i - 1] + f[i - 2];
}
printf("测试:\n");
for (int i = 0; i < 20; i++) {
key = (int)(rand() % 100);
index = Fibonacci_Search(a, length,key);
printf("key=%2d 在表中下标：%2d\n",key, index);
}
return 0;
}
测试结果
查找表
$ 0: 1 $ 1: 2 $ 2: 2 $ 3: 2 $ 4: 4 $ 5: 4 $ 6: 5 $ 7: 8 $ 8: 9 $ 9: 9
$10:12 $11:12 $12:16 $13:16 $14:25 $15:26 $16:27 $17:28 $18:28 $19:28
$20:28 $21:29 $22:29 $23:31 $24:32 $25:33 $26:37 $27:38 $28:39 $29:39
$30:40 $31:40 $32:41 $33:43 $34:43 $35:44 $36:45 $37:47 $38:47 $39:48
$40:50 $41:51 $42:51 $43:52 $44:52 $45:52 $46:52 $47:53 $48:53 $49:53
$50:54 $51:54 $52:55 $53:55 $54:55 $55:56 $56:57 $57:58 $58:58 $59:63
$60:63 $61:64 $62:65 $63:65 $64:65 $65:68 $66:69 $67:70 $68:70 $69:71
$70:71 $71:73 $72:73 $73:77 $74:77 $75:77 $76:78 $77:79 $78:81 $79:81
$80:81 $81:81 $82:84 $83:84 $84:84 $85:85 $86:85 $87:88 $88:89 $89:90
$90:92 $91:93 $92:93 $93:93 $94:94 $95:95 $96:95 $97:96 $98:98 $99:99
测试:
key=33 在表中下标：25
key= 7 在表中下标：-1
key=40 在表中下标：31
key=69 在表中下标：66
key=30 在表中下标：-1
key= 3 在表中下标：-1
key=24 在表中下标：-1
key=66 在表中下标：-1
key=27 在表中下标：16
key=14 在表中下标：-1
key= 0 在表中下标：-1
key=44 在表中下标：35
key=28 在表中下标：20
key=92 在表中下标：90
key=96 在表中下标：97
key=67 在表中下标：-1
key= 2 在表中下标： 2
key=30 在表中下标：-1
key=64 在表中下标：61
key=20 在表中下标：-1