顺序表查找(Sequential Search)又叫线性表查找，是最基本的查找法，从第一个开始到最后一个逐个与关键字比较。成功不成功都返回。

//顺序表查找
int SequentialSearch(int* a,int n, int key)
{
	for(int i=0;i<n;i++)
	{
		if(key==a[i])
		{
			return i;
		}
	}
	else
		return -1;
}
上面代码缺点是每次取i都要跟n 比较；
//顺序表查找优化
int SequentialSearch2(int* a,int n, int key)
{
	a[n]=key;
	int i=0;
	while(key != a[i])
	{
		i++;
	}
	return i;//返回n表示失败了
}
此时代码从尾部开始查找，这种查找避免了每次查找i跟n的比较 时间复杂度为O(n);

顺序表查找

有序表查找

对顺序表进行二分查找
索引顺序查找表

索引顺序查找表也就是分块查找
把线性表分为若干块，每一块的关键字都小于下一块的最小关键字。
索引按顺序排列进行二分查找，在对找到的块进行顺序查找

顺序表查找，逐一比较，它有以下算法

1.顺序查找

2.顺序查找优化（加了个哨兵）

 

代码：

/*
 * 顺序查找不等同与顺序表就已经是有序的了，这里需要注意
 * 时间复杂度为0(n)
 * 空间复杂度为1
 */
public class SequentialSearch {
	
	/*
	 * 顺序表查找算法
	 * @param a 数组
	 * @param n 数组大小
	 * @param key 要查找的关键字
	 * @return 返回查找的位置
	 */
	public int sequentialSearch1(int[] a, int n, int key) {
		for(int i = 0;i < n;i++) {
			if(a[i] == key) {
				return i;
			}
		}
		return 0;
		
	}
	
	/*
	 * 顺序表查找优化-有哨兵顺序查找
	 * 优化方向：设置一个哨兵解决不需要每次让i与n做比较
	 * 即不需要每次循环都判断i是否越界
	 * 
	 * @param a 数组
	 * @param n 数组大小
	 * @param key 要查找的关键字
	 * @return 返回查找的位置
	 */
	public int sequentialSearch2(int[] a, int n, int key) {
		//设置a[0]为关键字值，也就是哨兵
		a[0] = key;
		//从后往前查找
		int i = n;
		while(a[i] != key) {
			i--;
		}
		//返回0说明查找失败
		return i;
	}
}

 

静态查找
前言
顺序表查找
顺序查找
哨兵查找
有序表查找
折半查找
插值查找
斐波那契查找
真正实现代码功能
运行结果
后记

前言
搜索引擎就是利用了查找的技术，查找方式按照操作方式有两大种，分别是静态查找和动态查找。静态查找只做查找，动态查找在查找过程中插入不存在的元素，删除已存在的元素。

本篇只讨论有关静态查找的内容

找不到返回-1
顺序表查找
顺序表查找分为顺序查找和优化的哨兵查找。
顺序查找
int Sequential_Search(int *a,int n,int key)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(a[i]==key)
			return i;
	}
	return -1;

}

哨兵查找
在优化的查找中，设置了一个哨兵，免去了查找过程中每次比较后都要判断查找位置是否越界。总数据较多时，效率提高很大
int Sequential_Search1(int *a,int n,int key)
{
	int i;
	a[-1] = key;//设置哨兵
	i = n;
	while(a[i]!=key)
	{
		i--;
	}
	return i;//返回-1则说明查找失败
}

有序表查找
有序表就是有排列顺序的表

折半查找适用于数据量较大的

插值查找适用于表长比较大，关键字分布广的

斐波那契适用于数据分布极端不均匀的
折半查找
int Binary_Search(int *a,int n,int key)
{
	int low,high,mid;
	low = 0;//定义最低下标为记录首位
	high = 9;//定义最高下标为记录末尾
	while(low<=high)
	{
		mid = (low+high)/2;//折半
		if(key<a[mid])
			high = mid-1;
		else if(key>a[mid])
			low = mid+1;
		else
			return mid;
	}
	return -1;
}

插值查找
插值查找的核心在于插值的计算公式。查找关键字key与查找表中最大最小记录的关键字比较后的查找方法。

代码就是折半查找中注释折半那一行替换为查找这一行就行了
mid = low+(high-low)*(key-a[low])/(a[high]-a[low]);//插值

斐波那契查找
斐波那契查找利用了黄金分割率原理实现

查找的核心在于：

当key = a[mid]时，查找成功；
当key < a[mid]时，新范围是第low到mid-1个，此时范围个数为F[k-1]-1个；
当key 》 a[mid]时，新范围是第mid+1到high个，此时范围个数为F[k-2]-1个；

int Fibonacci_Search(int *a,int n,int key)
{

	int F[30];
	F[0] = 0;
	F[1] = 1;
	for(int m = 2;m<30;m++)
		F[m] = F[m-1]+F[m-2];//斐波那契数组

	int low,high,mid,i,k;
	low = 0;//定义最低下标为记录首位
	high = n;//定义最高下标为记录末尾
	k = 0;
	while(n>F[k]-1)//记录n位于斐波那契数列的位置
		k++;
	for(i=n;i<F[k]-1;i++)//将不满的数值补全
		a[i] = a[n];
	while(low<=high)
	{
		mid = low+F[k-1]-1;//计算当前分隔的下标
		if(key<a[mid])
		{
			high = mid-1;//最高下标调整到mid-1处
			k = k-1;//斐波那契下标减一位
		}
		else if(key>a[mid])//若查找记录大于分隔记录
		{
			low = mid+1;//最低下标调整到mid+1处
			k = k-2;//斐波那契下标减一二位
		}
		else
		{
			if(mid<=n)
				return mid;
			else
				return n;//若mid=n，说明是补全数值，返回n
		}
	}
	return -1;
}
}

真正实现代码功能
花了较长时间把这些代码的功能实现了。

注意创建一个比较自由的数组，我们可以用顺序表的结构体来表示数组，但是还有一种方法，与结构体表示有异曲同工之妙，首先创建一个数组，然后往其中填充数据，再用一个子函数求出数据长度。

顺序表数据是自己填充

有序表是系统自带，长度固定为9
#include<stdio.h>
#include<stdlib.h>

#define M 20

void Init(int *a);//初始化数组
void Display(int *a);//显示数组
int number(int *a);//求数据长度
int Sequential_Search(int *a,int n,int key);//顺序查找
int Sequential_Search1(int *a,int n,int key);//顺序哨兵查找
int Binary_Search(int *a,int n,int key);//有序表折半查找
int Interpolation_Search(int *a,int n,int key);//有序表插值查找
int Fibonacci_Search(int *a,int n,int key);//有序表斐波那契查找

int main()
{
	int i,x,n;
	int len;
	int a[20];
	Init(a);
	printf("顺序表为:");
	Display(a);
	len = number(a);
	printf("数据长度为%d\n",len);
	int b[12] = {1,16,24,35,47,59,62,73,88,99};
	printf("排序表为:");
	Display(b);
	while(1)
	{
		printf("1.顺序表查询 2.顺序表哨兵查询 3.有序表折半查找 4.有序表插值查找 5.有序表斐波那契查找\n");
		scanf("%d",&x);
		switch(x)
		{
		case 1:
			printf("顺序表查询的数:\n");
			scanf("%d",&n);
			i = Sequential_Search(a,len,n);
			printf("此数的数组下标：%d\n",i);
			break;
		case 2:
			printf("顺序表查询的数:\n");
			scanf("%d",&n);
			i = Sequential_Search1(a,len,n);
			printf("此数的数组下标：%d\n",i);
			break;
		case 3:
			printf("有序表查询的数:\n");
			scanf("%d",&n);
			i = Binary_Search(b,9,n);
			printf("此数的数组下标：%d\n",i);
			break;
		case 4:
			printf("有序表查询的数:\n");
			scanf("%d",&n);
			i = Interpolation_Search(b,9,n);
			printf("此数的数组下标：%d\n",i);
			break;
		case 5:
			printf("有序表查询的数:\n");
			scanf("%d",&n);
			i = Fibonacci_Search(b,9,n);
			printf("此数的数组下标：%d\n",i);
			break;
		}
	}
}

void Init(int *a)
{
	int i = 0;
	int x = 0;
	printf("请输入数据,-1时结束且长度不得大于20:\n");
	while(x!=-1)
	{
		scanf("%d",&x);
		if(x!=-1)
		{
			a[i] = x;
			i++;
		}
	}
	a[i] = '\0';
}

void Display(int *a)
{
	for(int i=0;a[i]!='\0';i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}

int number(int *a)
{
	int i;
	for(i =0;a[i]!='\0';)
	{
		i++;
	}
	return i;
}

int Sequential_Search(int *a,int n,int key)
{
	int i;
	for(i=0;i<n;i++)
	{
		if(a[i]==key)
			return i;
	}
	return -1;

}

int Sequential_Search1(int *a,int n,int key)
{
	int i;
	a[-1] = key;//设置哨兵
	i = n;
	while(a[i]!=key)
	{
		i--;
	}
	return i;//返回-1则说明查找失败
}

int Binary_Search(int *a,int n,int key)
{
	int low,high,mid;
	low = 0;//定义最低下标为记录首位
	high = 9;//定义最高下标为记录末尾
	while(low<=high)
	{
		mid = (low+high)/2;//折半
		if(key<a[mid])
			high = mid-1;
		else if(key>a[mid])
			low = mid+1;
		else
			return mid;
	}
	return -1;
}

int Interpolation_Search(int *a,int n,int key)
{
	int low,high,mid;
	low = 0;
	high = 9;
	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;
	}
	return -1;
}

int Fibonacci_Search(int *a,int n,int key)
{

	int F[30];
	F[0] = 0;
	F[1] = 1;
	for(int m = 2;m<30;m++)
		F[m] = F[m-1]+F[m-2];//斐波那契数组

	int low,high,mid,i,k;
	low = 0;//定义最低下标为记录首位
	high = n;//定义最高下标为记录末尾
	k = 0;
	while(n>F[k]-1)//记录n位于斐波那契数列的位置
		k++;
	for(i=n;i<F[k]-1;i++)//将不满的数值补全
		a[i] = a[n];
	while(low<=high)
	{
		mid = low+F[k-1]-1;//计算当前分隔的下标
		if(key<a[mid])
		{
			high = mid-1;//最高下标调整到mid-1处
			k = k-1;//斐波那契下标减一位
		}
		else if(key>a[mid])//若查找记录大于分隔记录
		{
			low = mid+1;//最低下标调整到mid+1处
			k = k-2;//斐波那契下标减一二位
		}
		else
		{
			if(mid<=n)
				return mid;
			else
				return n;//若mid=n，说明是补全数值，返回n
		}
	}
	return -1;
}

运行结果

后记
本篇确实是只用一片代码柔和了五个算法，实在有些罗嗦，但是功能确实是全部实现的。

今天的内容就是静态查找的基本操作及其内容，喜欢我的多多支持哦~