网站设计师加油站,茂港网站设计公司,手机网站开发设计,莱州市网站顺序查找
顺序查找是最简单的了#xff0c;属于无序查找算法#xff0c;它的原理就是从前往后一个一个的找#xff0c;如果找到了就返回它的位置#xff0c;否则就返回-1。
如果有多个相同元素的话#xff0c;返回第一个该元素的位置。
代码#xff1a;
#include…
顺序查找
顺序查找是最简单的了属于无序查找算法它的原理就是从前往后一个一个的找如果找到了就返回它的位置否则就返回-1。
如果有多个相同元素的话返回第一个该元素的位置。
代码
#includestdio.h
#define N 100
int main()
{int a[N],n,x;//x表示要查找的元素 scanf(%d %d,n,x);for(int i0;in;i){scanf(%d,a[i]);}int j;for(j0;jn;j){if(a[j]x)//如果找到直接跳出循环 break;}if(jn){printf(-1);//如果没找到就返回-1 }else{printf(%d ,j1);//返回它的位置即是第几个元素 }return 0;
}
运行 二分查找
二分查找Binary Search算法也叫折半查找算法针对有序查找算法即只适用于有序序列的查找。它的原理就是每次都通过跟区间的中间元素对比将待查找的区间缩小为之前的一半直到找到要查找的元素或者区间被缩小为 0。
代码
#includestdio.h
#define N 100
int main()
{int a[N],n,x;//x表示要查找的元素 scanf(%d %d,n,x);for(int i0;in;i){scanf(%d,a[i]);}int left0,rightn-1,mid;while(leftright){mid(leftright)/2;if(xa[mid]) break;if(xa[mid]) {leftmid1;}else{rightmid-1;}}if(leftright){printf(-1);//如果没找到就返回-1 }else{printf(%d ,mid1);//返回它的位置即是第几个元素 }return 0;
}
运行 插值查找
插值查找就是二分查找的改进其算法思路是一样的只不过二分查找是每次是从数组的中间位置查找的但是如果能在查找前较准确地预测关键字在数组中的位置的话效率就会大大提高。
插值查找其核心就在于插值的计算公式key-arr[left]/arr[right]-arr[left]。细看是不是key在整序列中的占比哟。所以mid的计算公式为 leftright-left*key-arr[left]/arr[right]-arr[left]。对比二分查找的mid right-left/2。
举个例子来理解一下1 2 3 4 5 6 查找元素3
使用插值查找公式0 5-0*3-1/6-12这样的话一次就找到了效率要高于二分查找。 对表长较长且关键字分分布比较均匀插值查找算法的平均性能要比二分查找要好的多。但是 如果表中 关键字分布极端不均匀 那么插值查找还不如折半查找呢。 代码和折半查找一模一样唯独mid的计算方式发生改变。
代码
#includestdio.h
#define N 100
int main()
{int a[N],n,x;//x表示要查找的元素 scanf(%d %d,n,x);for(int i0;in;i){scanf(%d,a[i]);}int left0,rightn-1,mid;while(leftright){midleft(right-left)*(x-a[left])/(a[right]-a[left]);if(xa[mid]) break;if(xa[mid]) {leftmid1;}else{rightmid-1;}}if(leftright){printf(-1);//如果没找到就返回-1 }else{printf(%d ,mid1);//返回它的位置即是第几个元素 }return 0;
}
运行
