静态查找C语言实现

#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define maxlen 100
int F[100];


int sequential_Search(int* a, int n, int key)//从头部开始查找
{
	int i;
	for (i = 1;i <= n;i++)
	{
		if (a[i] == key)
		{
			return i;
		}
	}
	return 0;
}

int sequential_Search2(int* a, int n, int key)//从尾部开始查找
{
	int i;
	i = n;
	a[0] = key;
	while (a[i] != key)
	{
		i--;
	}
	return i;
}

int binary_search(int* a, int n, int key) //折中查找
{
	int mid, low, high;
	low = 1;
	high = n;
	while (low<=high)
	{
		mid = (low + high) / 2;
		if (a[mid] > key)
		{
			high = mid-1;
		}
		else if (a[mid] < key)
		{
			low = mid+1;
		}
		else
		{
			return mid;
		}
	}
	return 0;
}

int interpolation_Search(int* a, int n, int key) //插值查找，适合均匀变化的数组
{
	int low, high, mid;
	low = 1;	/* 定义最低下标为记录首位 */
	high = n;	/* 定义最高下标为记录末位 */
	while (low <= high)
	{
		mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); /* 插值 */
		if (key < a[mid])		/* 若查找值比插值小 */
			high = mid - 1;		/* 最高下标调整到插值下标小一位 */
		else if (key > a[mid])/* 若查找值比插值大 */
			low = mid + 1;		/* 最低下标调整到插值下标大一位 */
		else
			return mid;		/* 若相等则说明mid即为查找到的位置 */
	}
	return 0;
}

int fibonacci_Search(int* a, int n, int key)
{
	int low, high, mid;
	low = 0;
	high = n;
	int k=0;
	int i;
	while (n>=F[k]-1)
	{
		k++;
	}
	for (i = n+1;i < F[k] - 1;i++)
	{
		a[i] = a[n];
	}
	while (low<=high)
	{
		mid = low + F[k - 1] - 1;
		if (a[mid] < key)
		{
			low = mid + 1;
			k = k - 2;
		}
		else if (a[mid] > key)
		{
			high = mid - 1;
			k--;
		}
		else
		{
			if (mid <= n)
			{
				return mid;
			}
			else
			{
				return n;
			}
		}
	}
	return 0;
}

int main()
{
	int a[maxlen + 1], i, result;
	int arr[maxlen] = { 0,1,16,24,35,47,59,62,73,88,99 };

	for (i = 1;i <= maxlen;i++)
	{
		a[i] = i;
	}
	a[0] = maxlen;

	F[0] = 0;
	F[1] = 1;
	for (int i = 2;i < 100;i++)
	{
		F[i] = F[i - 1] + F[i - 2];
	}

	result = sequential_Search(a, maxlen,35);
	printf("顺序查找:%d \n", result);
	result = sequential_Search(a, maxlen, 35);
	printf("顺序查找2:%d \n", result);
	 
	result = Binary_Search(arr, 10, 62);
	printf("折中查找:%d \n", result);


	result = interpolation_Search(arr, 10, 62);
	printf("插值查找:%d \n", result);

	result = fibonacci_Search(arr, 10, 62);
	printf("斐波那契查找:%d \n", result);
}