算法——查找算法
1、顺序查找：
定义：
顺序查找（Sequential Search） 又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
代码：
import java.util.Scanner;
import org.junit.jupiter.api.Test;
/**
* 顺序查找
* @author wydream
*
*/
public class SequelSearch {
public int search(int[] arr,int num) {
if(arr.length==0) {
return -1;
}
for(int i=0;i<arr.length;i++) {
if(arr[i]==num) {
return i;
}
}
return -1;
}
@Test
public void test() {
int[] arr={4,6,2,8,1,9,0,3};
Scanner input=new Scanner(System.in);
System.out.println("请输入你要查找的数:");
int num=input.nextInt();
int result=search(arr,num);
if(result==-1){
System.out.println("你输入的数不存在与数组中");
}
else {
System.out.println("你输入的数字存在，在数组中的位置是第："+(result+1)+"个");
}
}
}2、折半查找（二分查找）
定义：
折半查找（Binary Search） 技术，又称为：二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找区域无记录，查找失败为止
代码：
import org.junit.jupiter.api.Test;
/**
* 二分查找
* 1.循环实现
* 2.递归实现
* @author wydream
*
*/
public class BinarySearch {
//1.循环实现二分查找
public int rank(int[] arr,int num) {
int start=0;
int end=arr.length;
int mid=(start+end)/2;//中间数的下标
while(start<=end) {//退出循环的条件 若一直没找到这个数，则会退出循环
if(arr[mid]==num)
return mid;
else if(arr[mid]>num) {
end=mid-1;
}else {
start=mid+1;
}
mid=(start+end)/2;
}
return -1;
}
//2.递归实现二分查找
public int recursion(int[] arr,int num,int start,int end) {
int mid=(start+end)/2;
if(start==end&&arr[mid]!=num) {
return -1;
}
if(arr[mid]==num) {
return mid;
}else {
if(arr[mid]>num) {
end=mid-1;
return recursion(arr,num,start,end);
}else{
start=mid+1;
return recursion(arr,num,start,end);
}
}
}
//测试
@Test
public void testRank() {
int[] arr= {2,3,6,9,13,18,20,22,24,29,30,45,67,88};
int result=rank(arr,2);
if(result==-1) {
System.out.println("你要查找的数字不在该数组中");
}else {
System.out.println("你查找的数字在数组的第"+(result+1)+"位");
}
}
@Test
public void testRecursion() {
int[] arr= {2,3,6,9,13,18,20,22,24,29,30,45,67,88};
int result=recursion(arr,20,0,arr.length-1);
if(result==-1) {
System.out.println("你要查找的数字不在该数组中");
}else {
System.out.println("你查找的数字在数组的第"+(result+1)+"位");
}
}
}3、插值查找
定义：
插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式。插值计算公式：mid=start+(key-a[start])/(arr[end]-arr[start])*(end-start)；
代码（递归和非递归两种方法实现）：
import org.junit.jupiter.api.Test;
/**
* 插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式
* 插值计算公式：mid=start+(key-a[start])/(arr[end]-arr[start])*(end-start)；
* @author wydream
*
*/
public class InsertValueSearch {
//递归实现插值查找
public int recursionBinarySearch(int[] arr,int key,int start,int end) {
//当查找的值小于数组最小值,或者大于数组最大值,或者start>end时查找结束
if(key<arr[start]||key>arr[end]||start>end) {
return -1;
}
if(arr[start]==key) {
return start;
}
if(arr[end]==key) {
return end;
}
int mid = start+(end-start)*((key-arr[start])/(arr[end]-arr[start]));
if(arr[mid]>key) {
//说明key在前半部分
return recursionBinarySearch(arr,key,start,mid-1);
}
else if(arr[mid]<key) {
//说明key在后半部分
return recursionBinarySearch(arr,key,mid+1,end);
}else {
return mid;
}
}
//非递归实现插值查找
public int commonBinarySearch(int[] arr,int key) {
int start=0;
int end=arr.length-1;
if(key<arr[start]||key>arr[end]) {
return -1;
}
int mid = start+(end-start)*((key-arr[start])/(arr[end]-arr[start]));
while(start<=end) {
if(arr[mid]==key) {
return mid;
}else if(arr[mid]>key) {//说明查找的值在mid的前面
end=mid-1;
}else {//说明查找的值在mid的后面
start=mid+1;
}
mid=start+(end-start)*((key-arr[start])/(arr[end]-arr[start]));
}
return -1;
}
//递归测试
@Test
public void testRecursion() {
int[] arr= {1,2,4,5,6,7,8,9};
int result=recursionBinarySearch(arr,1,0,arr.length-1);
if(result==-1) {
System.out.println("你要查找的数不在该数组中");
}else {
System.out.println("你要查找的数在数组的第"+(result+1)+"个位置");
}
}
//非递归测试
@Test
public void testCommon() {
int[] arr= {1,2,4,5,6,7,8,9};
int result=commonBinarySearch(arr,1);
if(result==-1) {
System.out.println("你要查找的数不在该数组中");
}else {
System.out.println("你要查找的数在数组的第"+(result+1)+"个位置");
}
}
}4、斐波那契查找
定义：
1.斐波那契实在二分查找基础上，用斐波那契数列来进行分割 2.在斐波那契数列上找一个略大于查找元素表个数的值f(n) 3.将查找元素表个数扩充到f(n) 如果要补充元素用最后一个元素补充 4.完成后对f(n)个元素进行斐波那契分割,即分割成 前面f(n-1)个元素,后面f(n-2)个元素 5.对要查找元素的那个部分进行递归 6.就平均性能而言 优于折半查找 但是若一直在左边长半区查找则低于折半查找
代码：
import java.util.Arrays;
import org.junit.jupiter.api.Test;
/*
*----- 斐波那契查找------
* 1.斐波那契实在二分查找基础上，用斐波那契数列来进行分割
* 2.在斐波那契数列上找一个略大于查找元素表个数的值f(n)
* 3.将查找元素表个数扩充到f(n) 如果要补充元素用最后一个元素补充
* 4.完成后对f(n)个元素进行斐波那契分割,即分割成 前面f(n-1)个元素,后面f(n-2)个元素
* 5.对要查找元素的那个部分进行递归
* 6.就平均性能而言 优于折半查找 但是若一直在左边长半区查找则低于折半查找
* */
public class FibonacciSearch {
private static int maxsize=20;
//生成斐波那契数列
public int[] fibonaqie() {
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;
}
//查找
public int search(int[] arr,int key) {
int low=0;
int high=arr.length-1;
int k=0;//斐波那契分割数值下标
int mid=0;
int f[]=fibonaqie();
//获得斐波那契分割数值下标
while(high>f[k]-1) { //int [] a= {1,3,5,7,9,11,12}; 6
k++;
}
//利用Java工具类Arrays 构造新数组并指向 数组 arr[]
int[] temp=Arrays.copyOf(arr, f[k]);
//对新构造的数组进行 元素补充
for(int i=high+1;i<temp.length;i++) {
temp[i]=arr[high];
}
while(low<=high) {
//由于前面部分有f[k-1]个元素
mid=low+f[k-1]-1;
if(key<temp[mid]) {
high=mid-1;
/**
*
*全部元素=前部元素+后部元素
* 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
* */
k--;
}else if(key>temp[mid]) {//关键字大于切个位置元素 则查找后半部分
low=mid+1;
/***
* 全部元素=前部元素+后部元素
* f[k]=f[k-1]+f[k-2]
* 因为后部有f[k-2]个元素,所以可以继续拆分f[k-2]=f[k-3]+f[k-4]
* 即在f[k-2]的前部继续查找 所以k-=2
* 即下次循环 mid=f[k-1-2]-1
*/
k-=2;
}else {
if(mid<=high) {
return mid;
}else {
return high;
}
}
}
return -1;
}
@Test
public void test() {
int [] a= {1,3,5,7,9,11,12};
int i=search(a, 5);
System.out.println("5在："+(i+1));
int j=search(a, 12);
System.out.println("12在："+(j+1));
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-07-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录