1、概念:在一些有序的或无序的数据元素中,通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找,也就是给定一个值,在查找表中确定一个关键字等于给定值的记录或数据元素。
2、平均查找长度(后期可能会增加)
3、查找长度分为成功和失败两种
4、顺序查找
1、主要思想:将查找值顺序逐个与结点值进行比较,相等即为查找成功,否则查找失败
2、代码实现
int SqSearch(int a[],int len,int e) { int i = 0; while(i < len && a[i]!= e) { i++; } if(i >= len) { return 0;//没有找到 } return i+1;//返回逻辑序号 } //时间复杂度:O(n) //查找成功平均长度 (n+1)/ 2 //查找失败平均长度 n / 2
5、二分查找(折半查找)
1、算法思想:每次比较中间值和待查找值得大小,然后更新范围,最后确定具体位置(重点:序列有序)
2、代码实现
int BinSearch(int a[],int len,int e) { int i = 0; int j = len-1; int mid; while(i <= j) { mid = j/2; if(e > a[mid]) { i = mid +1; } else if(e < a[mid]) { j = mid-1; } else return mid+1; } return -1; } //时间复杂度:log2n //ASL成功:1/n累加(times*deepth) //ASL失败:1/n累加(fails*deepth) //以二叉树了理解,排序写完会重新更新这一块内容
6、分块查找
1、算法思想:
1、把表长为n的线性表分成m块,前m-1块记录个数为 t = n / m t=n/m t=n/m,第m块的记录个数小于等于t;
2、块间有序,块中无序
3、建立索引表,其中记录每个块的起始位置以及最大元素
4、在增加元素的时候,根据索引表就知道在哪一块,把数据加到相应的块就好,因为块内无序;在查找时,索引表过大可以使用二分查找,会找到块在顺序查找,可能不会比二分查找好,但是不需要数据完全有序
2、代码1
typedef struct { int key; int link; }IdxType; int IdxSearch(IdxType I[],int b,int a[],int len ,int k)//b是分的块数,a是原数组,I是索引表,len是a数组的长度,k是需要查找值 { int s; int l; int r; int mid; s = (len+b-1)/b;//注意啊,确实是向下取整, l = 0; r = b-1; int i; while(l <= r)//对索引表进行二分查找 { mid = l+(r-l)/2; if(I[mid].key >= k) { r = mid -1; } else { l = mid +1; } } i = I[r + 1].link; while(i <= I[r+1].link + s -1 && a[i] !=k)//块内顺序查找 { ++i; } if(i <= I[r+1].link +s -1) { return i+1;//索引值没有越界的时候,就返回他的逻辑位置 } return -1; }
3、代码2
#include<stdio.h> struct indexBlock//定义块的结构 { int key; int start; int end; }indexBlock[4]; int search(int key,int a[]); int main() { int i; int j = -1; int k; int key; int a[] = {12,25,33,36,57,146,219,254,315,336,358,795,876,951,999}; printf("已知有一组数:\n"); for(i = 0;i < 15;i++) { printf("%d ",a[i]); if((i+1)%5==0 && i < 14) { printf("|"); } } printf("\n"); //确定模块起始值和最大值 for(i = 0;i < 3;i++) { indexBlock[i].start = j+1; j++; indexBlock[i].end = j+4; j += 4; indexBlock[i].key = a[j];//确定每一块的最大值?//直接赋值因为数组初始化的时候块的最后一个值最大值,违背了块内无序啊 printf("indexBlock[%d].start = %d\n",i,indexBlock[i].start); printf("indexBlock[%d].end = %d\n",i,indexBlock[i].end); printf("indexBlock[%d].key= %d\n",i,indexBlock[i].key); } // printf("input the num you want to search:"); scanf("%d",&key); k = search(key,a); // if(k > 0) { printf("Find,Location is %d\n",k+1); } else { printf("Search Fail!\n"); } return 0; } int search(int key,int a[]) { int i,startvalue; i = 0; while(i < 3 && key > indexBlock[i].key) { i++; } if(i >= 3) { return -1; } startvalue = indexBlock[i].start; while(startvalue <= indexBlock[i].end && a[startvalue] != key) { startvalue++; } if(startvalue > indexBlock[i].end) { startvalue = -1; } return startvalue; }
标签:分块,int,一之,mid,查找,key,printf,indexBlock From: https://www.cnblogs.com/gunancheng/p/17470335.html