文章目录

查找

查找是在大量的信息里面寻找一个特定的信息元素

（1）静态查找和动态查找；

静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表

（2）无序查找和有序查找。

无序查找：被查找数列有序无序均可；

有序查找：被查找数列必须为有序数列。

二分查找（折半查找）

说明：元素必须是有序的，如果是无序的则要先进行排序操作

基本思想：

也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

时间复杂度

共有n个元素，需要搜索n/2,n/4,n/8…n/2^k…

n/2^k = 1

k = log2n(以2为底，n为对数)

O(n) = O（log2n）或者O(n) = O(logn)

#include <stdio.h>int BinarySearch(int *arr,int val,int len){int low,high,mid;low=0;high=len-1;while(low<=high){mid = low + (high - low)/2;if(arr[mid] == val)return mid;else if(val < arr[mid])high = mid-1;else if(val > arr[mid])low = mid+1;}return -1;}int BinarySearch1(int *a,int val,int low,int high){if(low > high) return -1;int mid = low + (high-low)/2;if(a[mid] == val) return mid;if(val < a[mid]) return BinarySearch1(a,val,low,mid-1);if(val > a[mid]) return BinarySearch1(a,val,mid+1,high);}int main(int argc, char const *argv[]){int arr[] = {12 ,22 ,28 ,29 ,35 ,36 ,37 ,39 ,69 ,453};int len=sizeof(arr)/sizeof(*arr);int num,i;for(i=0;i<len;i++)printf("%d ",arr[i]);printf("\n");// num = BinarySearch(arr,69,len);num = BinarySearch1(arr,69,0,len-1);printf("%d\n",num);return 0;}

插值查找

（1）说明：

在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？

打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。

同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。

经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下

mid=(low+high)/2, 即mid=low+1/2*(high-low)

通过类比，我们可以将查找的点改进为如下：

mid=low+(key-a[low])/(a[high]-a[low])*(high-low)

#include <stdio.h>//插值查找int InsertSearch(int *a, int val, int low, int high){int mid = low+(val-a[low])/(a[high]-a[low])*(high-low);if(a[mid]==val) return mid;if(a[mid]>val) return InsertSearch(a, val, low, mid-1);if(a[mid]<val) return InsertSearch(a, val, mid+1, high);}int main(int argc, char const *argv[]){int arr[] = {12 ,22 ,28 ,29 ,35 ,36 ,37 ,39 ,69 ,453};int len=sizeof(arr)/sizeof(*arr);int num,i;for(i=0;i<len;i++)printf("%d ",arr[i]);printf("\n");num = InsertSearch(arr,69,0,len-1);printf("%d\n",num);return 0;}

斐波拉契查找

斐波那契查找（黄金分割法查找）

​ 斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····。在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

​ 斐波那契查找是在二分查找的基础上根据斐波那契数列进行分割。在斐波那契数列找一个等于大于查找表中元素个数的数F(n),将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足F(n)个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F(n-1)个元素，后半部分F(n-2)个元素，找出要查找的元素在那一部分并递归，直到找到。斐波那契查找的时间复杂度是O(log2n)。

斐波那契查找算法的核心在于：

1）当key=a[mid]时，查找就成功；

2）当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为

F[k-1]-1个；

3）当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为

F[k-2]-1个。

（1）我们需要先递归实现斐波拉契数列，然后根据原数组的大小计算斐波拉契数列的k值；

（2）数组扩容条件是：增大 k 值（索引从 0 开始），使得数组长度刚好大于或者等于斐波那契数列中的 F[k]-1 ，我们定义临时数组 temp ，temp 后面为 0 的元素都按照数组最大元素值填充；

（3）mid值的确定：mid = low + f[k - 1] - 1 ，即用黄金分割点确定 mid 的值；

（4）value<temp[mid] ：目标值在黄金分割点的左边，因为全部元素 = 前面的元素 + 后边元素即 f[k] = f[k-1] + f[k-2]，又前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]，即下次循环有mid=low+f[k-1-1]+1，即需要k-=1；

value> temp[mid] ：目标值在黄金分割点的右边。因为全部元素 = 前面的元素 + 后边元素即 f[k] = f[k-1] + f[k-2]，又前面有 f[k-2]个元素,所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]，即下次循环有mid=low+f[k-1-2]+1，即需要k-=2；

value== temp[mid] ：找到目标值，因为数组经历过扩容，后面的值其实有些是多余的，mid 可能会越界（相对于原数组来说）则有：

1）mid <= high ：证明 mid 索引在原数组中，返回 mid；

2）mid > high 时，证明 mid 索引已经越界（相对于原数组来说），返回 high；

（5）若没有找到则返回-1。

#include<stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>void print_arr(int *a,int len);// 通过循环来找到第几个斐波那契数大于numberstatic int getFibonacci_size__(int size){int i=2,a=1,b=1,c;for(;c<size;){c=a+b;a=b;b=c;i++;}return i;}//构建fibo数组static void fibonacci_arr__(int *fibo,int size){fibo[0]=1;fibo[1]=1;for(int i=2;i<size;i++)fibo[i]=fibo[i-2]+fibo[i-1];}int FibonacciSearch(int *arr,int size,int key){int fiboSize = getFibonacci_size__(size);//测算斐波那契数组的大小//构建一个斐波拉契数组int* fibo = calloc(fiboSize, sizeof(int));//开辟一个用于存储斐波那契数列的数组空间fibonacci_arr__(fibo,fiboSize);int low=0;/*定义最低下标为记录首位 */int high=size-1;int i,k=0;//表示斐波那契分割数值的下标int mid;while(high>fibo[k]-1)//获取到斐波那契分割数值的下标++k;//扩展数组a到fibo[k]-1的长度int* tmp = calloc(fibo[k] - 1, sizeof(int));//创建一个与当前斐波那契数（减一是从下标0开始）长度的数组空间memcpy(tmp,arr,size*sizeof(int));//将不满的数值补全for(i=size;i<fibo[k]-1;i++){tmp[i] = arr[high];}// print_arr(tmp,fibo[k]-1);while(low <= high){mid = low+fibo[k-1]-1;if(key > tmp[mid]){low=mid+1;k-=2;//fibo[k-2]-1//为什么是k -=2//说明//1. 全部元素 = 前面的元素 + 后边元素//2. f[k] = f[k-1] + f[k-2]//3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]//4. 即在f[k-2] 的前面进行查找 k -=2//5. 即下次循环 mid = f[k - 1 - 2] - 1}else if(key < tmp[mid]){high = mid-1;k--;//fibo[k-1]-1//为甚是 k--//说明//1. 全部元素 = 前面的元素 + 后边元素//2. f[k] = f[k-1] + f[k-2]//因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]//即 在 f[k-1] 的前面继续查找 k--//即下次循环 mid = f[k-1-1]-1}else{free(tmp);tmp=NULL;return (mid>=size)?high:mid;// if(mid <= size)// {// return mid;//若相等则说明mid找到target// }// else// {// return high;//mid >= n,说明是扩展的数值返回n-1// }}}free(tmp);return -1;}void ShellSort(int *a,int len){int gap,i,j,target;for(gap=len/2;gap>0;gap/=2){for(i=gap;i<len;i++){target=a[i];j=i-gap;while(j>-1 && a[j]>target){a[j+gap]=a[j];j-=gap;}a[j+gap]=target;}}}void swap(int *a,int *b){int tmp=*a;*a=*b;*b=tmp;}void quick_sort1(int *nums, int l, int r) {if (l + 1 >= r) return;int first = l, last = r - 1, key = nums[first];while (first < last){while(first < last && nums[last] >= key)last--;printf("(%d %d)",nums[first],nums[last]);nums[first] = nums[last];while (first < last && nums[first] <= key) first++;printf("(%d %d)",nums[last],nums[first]);nums[last] = nums[first];}nums[first] = key;quick_sort1(nums, l, first);quick_sort1(nums, first + 1, r);}void print_arr(int *a,int len){for(int i=0;i<len;i++)printf("%d ",a[i]);printf("\n");}void quick_sort(int *a,int low,int high){if(low>=high) return;int first=low;int last=high-1;int key=a[low];//基准值while(first<last){while(a[last] >= key && first < last)last--;while(a[first] <= key && first < last)first++;if(first!=last)swap(&a[first],&a[last]);elseswap(&a[low],&a[last]);//基准值交换}quick_sort(a,low,first);quick_sort(a,first+1,high);}void RandomArr(int **arr,int *len){srand((unsigned)time(NULL));*len = random()%1000;*arr = malloc(sizeof(int)*(*len));for(int i=0;i<(*len);i++)(*arr)[i]=random()%1000;}int BinarySearch(int *a,int val,int low,int high){int mid;while(low<=high){mid=low+(high-low)/2;if(a[mid]==val)return mid;if(val < a[mid])high=mid-1;if(val > a[mid])low=mid+1;}return -1;}int main(int argc, char const *argv[]){int *arr;int len;int num;RandomArr(&arr,&len);print_arr(arr,len);printf("\n");quick_sort(arr,0,len);print_arr(arr,len);printf("请输入查找数字:");scanf("%d",&num);printf("index %d \n",BinarySearch(arr,num,0,len));printf("index %d \n",FibonacciSearch(arr,len,num));return 0;}

总结：

折半查找是进行加法与除法运算（mid=(low＋high)/2），插值查找进行复杂的四则运算（mid=low＋(high-low)*(key-a[low])/(a[high]-a[low])），而斐波那契查找只是最简单加减法运算（mid=low＋F[k-1]-1）。

斐波那契查找法在核心算法上，只有赋值与减法运算，而对半查找有加法和除法，插值查找有四则运算，因为除法比加减法消耗的时间更多，在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。