三种常用的查找算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了三种常用的查找算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4980字，纯文字阅读大概需要8分钟。
内容图文
在最近的复习中，我复习三种常用的查找算法，它们分别是:
1 线性查找
2 二分查找
3 插值法
4 斐波那契查找
线性查找
首先我们进行线性查找的讨论，对于线性查找，我们所做的操作就遍历数组同时逐一比对找出相匹配的元素，具体代码如下
public int search(int[] arr,int value)
{
for(int i=0;i<arr.length;i++)
{
if(arr[i]==value)
{
return i;
}
}
return -1;s
}
又上述代码我们不难理解，线性查找就是遍历数组的同时逐一比对数组的值和要查找的值，如果相同则就返回对应的数组下标
二分查找
对于二分查找，我们首先计算mid的值，在此演示中，我们设置的mid值为(left+right)/2,如果要搜索的值大于数组下标为mid的值，则就将left的值设置为mid+1,继续遍历，如果要插入的值小于数组下标为mid的值，则就将right的值设置为mid-1,继续遍历，重复上述操作，直到找到对应的数组的下标为止，当发生left>right时，则说明数组中并没有要搜索的值，此时我们返回-1并结束循环。
public static int binarySearch(int[] arr,int left,int right,int findVal)
{
if(left>right)
{
return -1;
}
int mid=(left+right)/2;
int midVal=arr[mid];
if(findVal>midVal)
{
return binarySearch(arr,mid+1,right,findVal);
}else if(findVal<midVal)
{
return binarySearch(arr,left,mid-1,findVal);
}else{
return mid;
}
}
//第二种方式是找出所有对应的数据才停止
public static List<Integer> binarySearch2(int[] arr,int left,int right,int findVal)
{
if(left>right)
{
return new ArrayList<Integer>();
}
int mid=(left+right)/2;
int midVal=arr[mid];
if(findVal>midVal)
{
return binarySearch2(arr,mid+1,right,findVal);
}else if(findVal<midVal)
{
return binarySearch2(arr,left,mid-1,findVal);
}else{
List<Integer> list=new ArrayList<Integer>();
int temp=mid-1;
while (true)
{
if(temp<0||arr[temp]!=findVal)
{
break;
}
//否则就把temp放入到集合中
list.add(temp);
temp-=1;
}
list.add(mid);
temp=mid+1;
while (true)
{
if(temp>arr.length-1||arr[temp]!=findVal)
{
break;
}
//否则就把temp放入到集合中
list.add(temp);
temp+=1;
}
return list;
}
}
在经过分析时，我们发现搜索边缘的操作对于二分查找太过繁琐，所以我们引入插值法来进行搜索
插值法
插值法与二分查找相同，不过mid值有所改变
/**
* 插值法和二分查找法一样，查找数组必须是有序的
* @param arr
* @param left
* @param right
* @param findVal
* @return
*/
public static int insertValueSearch(int[] arr,int left,int right,int findVal)
{
if(left>right||findVal<arr[0]||findVal>arr[arr.length-1])
{
return -1;
}
int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
int midVal=arr[mid];
if(findVal>midVal)
{
return insertValueSearch(arr,mid+1,right,findVal);
}else if(findVal<midVal)
{
return insertValueSearch(arr,left,mid-1,findVal);
}else{
return mid;
}
}
与二分查找方法不同是，插值法的mid等于low+(high-left)*(findVal-arr[low])/(arr[high]-arr[low])，我们在此基础上继续查找边缘位,如有一个大小为100的数组，第一位是0，最后一位是100，我们使用该方法查找0 100时会发现，我们第一次求出的mid的值就是对应的下标，所以插值法简化了二分查找。
斐波那契查找
斐波那契查找与二分查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1;（n为数组的大小，如果数组大小小于F(k)-1,则我们会将数组填充，即拿数组最后一位填充，直到n大于等于F(k)-1时)
开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种
1）相等，mid位置的元素即为所求
2）key>arr[mid],low=mid+1,k-=2;说明:low=mid+1说明待查找的元素在[mid+1,hign]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-（F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找
3) key<,arr[mid],high=mid-1,k-=1;说明:low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找
private static int maxSize=20;
public static void main(String[] args)
{
int[] arr={1,8,10,89,1000,1234};
}
//因为后面我们的mid=low+F(k-1)-1,需要使用斐波那契数列，因此我们需要先获取到一个斐波那契数列
//非递归方法获取斐波那契数列
public static int[] fib()
{
int[] f=new int[maxSize];
f[0]=1;
f[1]=1;
for(int i=2;i<maxSize;i++)
{
f[i]=f[i-1]+f[i-2];
}
return f;
}
//编写斐波那契查找算法
//使用非递归的方式编写算法
/**
*
* @param a 数组
* @param key 我们需要的关键码(值)
* @return 返回对应的下标，如果没有返回-1
*/
public static int fibSearch(int[] a,int key)
{
int low=0;
int high=a.length-1;
int k=0;//表示斐波那契分割数值的下标
int mid=0;//存放mid的值
int f[]=fib();//获取到斐波那契数列
while (high>f[k]-1)
{
k++;
}
//因为f[k]的值可能大于数组长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp
//不足的部分用0填充
int[] temp= Arrays.copyOf(a,f[k]);
//实际上需求使用a数组最后的数填充temp
for(int i=high+1;i<temp.length;i++)
{
temp[i]=a[high];
}
//使用while来循环处理，找到我们的数key
while (low<=high)
{
//只要这个条件满足就可以找
mid=low+f[k-1]-1;
if(key<temp[mid])
{
//我们应该继续向数组的左边查找
high=mid-1;
//为什么是k--
//说明:
//1 全部的元素=前面的元素+后面的元素
//2 f[k]=f[k-1]+f[k-2]
//因为前面有f[k-1]个元素，所以我们可以继续拆分
//即在f[k-1]的前面继续查找，即下次循环mid=f[k-1-1]-1
k--;
}else if(key>temp[mid])
{
//说明我们应该向数组的右边进行查找
low=mid+1;
//说明:
//1 全部的元素=前面的元素+后面的元素
//2 f[k]=f[k-1]+f[k-2]
//3 因为后面有f[k-2]个元素
//即在f[k-2]的前面可以继续进行查找k-=2
//即下次循环mid=f[k-1-2]-1
k-=2;
}else{
//需要确定返回的是哪个下标
if(mid<high)
{
return mid;
}else {
return high;
}
}
}
return -1;
}
内容总结
以上是互联网集市为您收集整理的三种常用的查找算法全部内容，希望文章能够帮你解决三种常用的查找算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。