17-数据结构-查找-（顺序、折半、分块）

简介：查找，顾名思义，是我们处理数据时常用的操作之一。大概就是我们从表格中去搜索我们想要的东西，这个表格，就是所谓的查找表（存储数据的表）。而我们怎么设计查找，才可以让计算机更快的去找到筛选我们所需要的信息呢，因此，关于怎么设计查找，就有了很多道道了。

比如，单纯的掰着手指头去算，一个一个查，这是顺序查找；又比如，我知道了一个有序数据的最大最小的下标，我直接每次看这组数据中间的值，就跟数字爆炸一样，1和10，我猜5，猜大了，那我就从6和10中间再说他们的中间值8，这样每次可以省一半的时间，这是折半查找；再者数据特别大，我每次查找要么挨个算，要么每次省一半，所需时间还很长，这时候我们就需要分块查找了，它用的时索引结构。索引，也就相当于书的目录，我们去读一本书想读的内容，首先先去目录去找它在第几章，随后在在那一章的第一页开始往下找。分块查找就是这样的，它显示分成块，每一块的第一个下标为该块在索引表的标记，分块查找的特点就是，索引表中是有序的，但块间无序的。

一、顺序查找

1.1简介：

1.2代码：

1.3实现

二、折半查找

2.1简介：

2.2折半思想代码：

2.3.折半的判断树

三、分块查找

3.1简介

一、顺序查找

1.1简介：

顺序查找，一般在线性表中进行查找。查找对象的存储结构适用于顺序表和链表。

线性表的顺序表中，分为有序和无序两种情况。

哨兵思想：就是在数组的开头第一个位置，或结尾第一个位置，不存放数据，从下标1开始存放，给每次需要对比的数据，放在哨兵位置，即下标0处，与之对比。这样可以避免越界。

        无序的话，则是从头到尾挨个遍历因此时间复杂度为O（n）。

        平均查找长度：

         查找成功： $\frac{n*(n+1))}{2}$ *   $\frac{1}{n}$ = $\frac{n+1}{2}$ ，前面是查找每一个数时的查找次数的总数，是个等差数列，后面乘上每个数被查找的概率，一般都是 $\frac{1}{n}$ ,即平分。

查找失败：就是给数组遍历，遍历到数据的下一位时发现找不到了，所以为n+1即可。

有序的话，类似于二叉排序树，它可以减少查找失败时的时间，因为有序，当我找的值，遍历到比前一个大，比后一个小时，那么就查找失败了，后面不用再看了。

平均查找长度：

查找成功：与无序一样， $\frac{n*(n+1))}{2}$ * $\frac{1}{n}$ = $\frac{n+1}{2}$ 。

查找失败：（ $\frac{n*(n+1))}{2}$ +n）* $\frac{1}{n+1}$ = $\frac{n}{2}\dotplus \frac{1}{n+1}$ ,，长方形为不存在的数据范围，查找这些范围，就算失败，后面就不用找了。如图，失败总次数为：1+2+3+3，1+2+3为等差数列，后面再加个3为结尾处无穷的情况。

1.2代码：

这里实现了顺序表的顺序查找

主要顺序查找思想：

//查找
int SeqSearch(SSTable* s,int key)
{//哨兵处，放进需要对比的值 s->data[0]=key;int i;//随后，从表尾进行遍历对比 i=s->tabLen;//不等于key的时候就一直递减 while(s->data[i]!=key){i--;}//如果找到了，则返回i，如果没找到，即最后i=0，跟哨兵坐标相等了，则失败 return i;	
}

#include <stdio.h>
#include <string.h>
#include <malloc.h>
//顺序查找结构体
typedef struct 
{int *data; //动态一维数组 int tabLen;//表长度 }SSTable;//顺序查找表 
//初始化顺序查找表 
void InitSSTable(SSTable *s)
{printf("输入表长\n");int k;scanf("%d",&k);s->tabLen=k;s->data=(int*)malloc(sizeof(int)*s->tabLen);
}
//查找
int SeqSearch(SSTable* s,int key)
{s->data[0]=key;int i;i=s->tabLen;while(s->data[i]!=key){i--;}return i;	
}
void CreatSSTable(SSTable *s)
{printf("表长为%d\n",s->tabLen);int i=1;printf("请给数组赋值\n");while(i<s->tabLen){int x;scanf("%d",&x);s->data[i]=x;	i++;}
}  int main()
{SSTable s;InitSSTable(&s);CreatSSTable(&s);int pos;int key;printf("请输入要查找的值\n");scanf("%d",&key);pos=BinarySearch(s,key); if(pos!=0)printf("%d在表中的下标为%d\n",key,pos);elseprintf("表中没有你要找的数据\n");return 0;}

1.3实现

二、折半查找

2.1简介：

折半查找，又叫二分查找，它仅适用于有序的顺序表，注意两个特点：1.有序；2.顺序表，进行随机存取操作时。折半字面意思，纸每次对折一半，就跟数字爆炸一样，每次我猜数字都从范围内的中间值猜，猜大猜小，再去另一个区域去猜。

2.2折半思想代码：

就是对有序的一维数组，进行折半划分。先定义两个标记遍历。low和high，low在数据最左侧开始，high在数据最右侧，high和low为数组下标，因此high=n-1；数组长度减1.随后进行while循环，循环为low<=high,随后进入循环，开始，先给mid跟新值，mid=（low+high）/2,我们通过mid去看数组中mid处的值，与key对比，如果相等，则返回，如果小于key，说明找的mid偏小了，所以在右区域去找，此时更新low即可，low=mid+1;同理如果大于key，说明大了，更新high=mid-1；

//二分查找
int BinarySearch(SSTable s,int key)
{int low=0;int high=s.tabLen-1;int mid=0;while(low <= high){printf("mid=%d\n",mid);mid=(low+high)/2;if(s.data[mid]==key)return mid;else if(s.data[mid]<key){low=mid+1;	}elsehigh=mid-1;			}return 0;	
}

2.3.折半的判断树

判断树，顾名思义，就是一个二叉树，通过二分法，去不断化分成两块。每个结点为mid处的值。先后顺序为，先记录low和high的初始值，当low<=high时，随后进行折半查找，先更新mid值 $\frac{low+high}{2}$ ,然后看数组mid处的值，与我们查找数对比，大或者小，进行high或low的更新即可。注：每次更新mid时，所得的运算结果，就是代码思想时所得结果，即3/2=1, 5/3=1，只保留整数位，