1 顺序查找
算法思路：
对于任意一个序列，从一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
代码：
#include <stdio.h> #include <stdlib.h> #define keyType int //2021.05.24 typedef struct { keyType key;//查找表中每个数据元素的值 }ElemType; typedef struct { ElemType *elem;//存放查找表中数据元素的数组 int length;//记录查找表中数据的总数量 }SSTable; //创建查询数据 void Create(SSTable **st,int length) { (*st)=(SSTable*)malloc(sizeof(SSTable)); (*st)->length=length; (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType)); printf("输入表中的数据元素：\n"); //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据 for (int i=1; i<=length; i++) { scanf("%d",&((*st)->elem[i].key)); } } //顺序查找函数，其中key为要查找的元素 int Search_seq(SSTable *str,keyType key) { //str->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置，起监视哨的作用 int len = str->length; //从最后一个数据元素依次遍历，一直遍历到数组下标为0 for(int i=1; i<len+1; i++) //创建数据从数组下标为1开始，查询也从1开始 { if(str->elem[i].key == key) { return i; } } //如果 i=0，说明查找失败；查找成功返回要查找元素key的位置i return 0; } int main() { SSTable *str; int num; printf("请输入创建数据元素的个数：\n"); scanf("%d",&num); Create(&str, num); getchar(); printf("请输入要查找的数据：\n"); int key; scanf("%d",&key); int location=Search_seq(str, key); if (location==0) { printf("查找失败"); }else{ printf("要查找的%d的顺序为：%d",key,location); } return 0; }
2 二分查找（折半查找）
算法思路：
确定查找范围low=0，high=N-1，计算中项mid=（low+high）/2。
若mid==x或low>=high,则结束查找；否则，向下继续。
若amid<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给low，并重新计算mid，转去执行步骤2；若mid>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给higt，并重新计算mid，转去执行步骤2。
说明：
查找元素必须是有序的，如果是无序的则要先进行排序操作。
在做查找的过程中，如果 low 指针和 high 指针的中间位置在计算时位于两个关键字中间，即求得 mid 的位置不是整数，需要统一做取整操作。
折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
——《大话数据结构》
代码：
#include <stdio.h> #include <stdlib.h> #define keyType int typedef struct { keyType key;//查找表中每个数据元素的值 }ElemType; typedef struct { ElemType *elem;//存放查找表中数据元素的数组 int length;//记录查找表中数据的总数量 }SSTable; //创建查询数据 void Create(SSTable **st,int length) { (*st)=(SSTable*)malloc(sizeof(SSTable)); (*st)->length=length; (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType)); printf("输入表中的数据元素：\n"); //根据查找表中数据元素的总长度，在存储时，从数组下标为 1 的空间开始存储数据 for (int i=1; i<=length; i++) { scanf("%d",&((*st)->elem[i].key)); } } //折半查找函数 key为要查找的元素 int Search_Bin(SSTable *str,keyType key) { int low=1;//初始状态 low 指针指向第一个关键字 int high=str->length;//high 指向最后一个关键字 int mid; while (low<=high) { mid=(low+high)/2;//int 本身为整形，所以，mid 每次为取整的整数 if(str->elem[mid].key==key)//如果 mid 指向的同要查找的相等，返回 mid 所指向的位置 { return mid; } else if(str->elem[mid].key>key)//如果mid指向的关键字较大，则更新 high 指针的位置 { high=mid-1; } //反之，则更新 low 指针的位置 else { low=mid+1; } } return 0; } int main() { SSTable *str; int num; printf("请输入创建数据元素的个数：\n"); scanf("%d",&num); Create(&str, num); getchar(); printf("请输入要查找的数据：\n"); int key; scanf("%d",&key); int location=Search_Bin(str, key); if (location==0) { printf("没有查找到"); }else{ printf("要查找的%d的顺序为：%d",key,location); } return 0; }
3 插值查找
插值查找基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找
算法思路：
确定查找范围low=0，high=N-1，计算中项mid=low+(key-a[low])/(a[high]-a[low])*(high-low)。
若mid==x或low>=high,则结束查找；否则，向下继续。
若amid<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给low，并重新计算mid，转去执行步骤2；若mid>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给higt，并重新计算mid，转去执行步骤2。
说明：
插值查找是基于折半查找进行了优化的查找方法。
当表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能要比折半查找要好得多。
代码：
#include<stdio.h> int array[10] = { 1, 4, 9, 16, 27, 31, 33, 35, 45, 64 }; int InsertionSearch(int data) { int low = 0; int high = 10 - 1; int mid = -1; int comparisons = 1; int index = -1; while(low <= high) { printf("比较 %d 次\n" , comparisons ); printf("low : %d, list[%d] = %d\n", low, low, array[low]); printf("high : %d, list[%d] = %d\n", high, high, array[high]); comparisons++; mid = low + (((double)(high - low) / (array[high] - array[low])) * (data - array[low])); printf("mid = %d\n",mid); // 没有找到 if(array[mid] == data) { index = mid; break; } else { if(array[mid] < data) { low = mid + 1; } else { high = mid - 1; } } } printf("比较次数: %d\n", --comparisons); return index; } int main() { int location = InsertionSearch(27); //测试代，查27，可以找到 if(location != -1) { printf("查找元素顺序为: %d\n" ,(location+1)); } else { printf("没有查找到"); } return 0; }
