查找算法_无序查找算法

1，预备知识

• 在学习查找算法之前，我们要先了解查找表
• 查找表：由同一类型的数据（或记录）构成的集合，查找算法解决的问题就是，如何快速的在查找表中找到我们想要的数据或者记录
• 查找表分类：静态查找表和动态查找表
• 静态查找表：只做查找操作的查找表
• 动态查找表：在查找的过程中同时对表进行插入或者删除操作的表
  

1，常用查找算法概述

• 常用查找算法可分为两种：无序查找和有序查找
• 无序查找：查找数列中的数是无序的，
• 有序查找：查找数列是已经按照一定的规律排好序了，常见算法中大多都是无序查找
• 常用的查找算法：
  顺序查找（线性查找），类型：无序查找
  二分查找（折半查找），类型：有序查找
  插值查找 ，类型：有序查找
  斐波那契查找 ，类型：有序查找
• 不常用的查找算法（本次不做探讨）：
  树表查找
  分块查找
  哈希查找

2，常用查找算法详解

2.1，无序查找

类型：

• 无序查找
• 查找表为线性表，无序

算法描述

• 无序查找也称为线性查找，是最基本的查找技术。
• 它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，如果某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
• 注意：该算法的时间复杂度为O(n)。当n很大时，查找效率不高。

Java代码实现

 /**
     * 顺序查找
     * @param arr：无序查找表
     * @param key：待查找的关键字
     * @return：关键字的索引
     */
    public static int sequenceSerach(int[] arr,int key ){
        for(int i=0;i<arr.length;i++){
            if(arr[i]==key){
                return i;//查找到返回索引
            }
        }
        return -1;//查找不到返回-1
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2，二分查找（binarySearch）

类型：

• 有序查找
• 查找表为线性表，有序

算法描述

• 在有序表中，取中间的记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功
• 若给定值小于中间记录的关键字，则在中间记录的左半区域继续查找
• 若给定值大于中间记录的关键字，则在中间记录的右半区域继续查找
• 不断重复上述过程，直到查找成功，或者将表查询一遍无记录，查找失败

Java代码实现

• 不使用递归的情况

 /**
     * 二分查找
     * @param arr：有序的线性查找表
     * @param key：待查找的关键字
     * @return：关键字的索引
     */
    public static int binarySearch(int[] arr,int key){
        int left=0;//有序表的第一个索引
        int right=arr.length-1;//有序表第最后一个索引
        while(left<=right){
            int mid=(left+right)/2;//二分位置
            if(arr[mid]>key){//大于则向左查
                right=mid-1;
            }else if(arr[mid]<key){//小于则向右查
                left=mid+1;
            } else{//等于则返回索引
               return mid;
            }
        }
        return -1;//未查到返回-1
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 使用递归的情况

/**
     * @param arr：有序的线性查找表
     * @param low：左边索引
     * @param height：右边索引
     * @param key：待查找的关键字
     * @return：关键字的索引
     */
    public static int binarySearch(int[] arr,int low,int height,int key) {
        int left=low;
        int right=height;
        int mid=(left+right)/2;
        if(left<=right){//递归退出条件
            if(arr[mid]>key){//大于则向左递归
                return binarySearch(arr,low,mid-1,key);
            }else if(arr[mid]<key){//小于则向右递归
                return binarySearch(arr,mid+1,height,key);
            } else{//等于则返回索引
                return mid;
            }
        }
        return -1;未查到返回-1
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.3，插值查找（ insertionSearch）

类型

• 有序查找
• 查找表为线性表，有序

算法描述

• 插值查找是对二分查找的一种优化
• 核心就是插值公式，对二分查找的公式进行修改，具体如下：
  
• 只需要在二分查找的基础上，对计算mid公式进行修改即可

Java代码实现

• 不使用递归的情况

/**
     * 插值查找
     * @param arr：有序的线性查找表
     * @param key：待查找的关键字
     * @return：关键字的索引
     */
    public static int insertionSearch(int[] arr,int key){
        int left=0;//有序表的第一个索引
        int right=arr.length-1;//有序表第最后一个索引
        while(left<=right){
            int mid=left+((key-arr[left])/(arr[right]-arr[left]))*(right-left);
            if(arr[mid]>key){//大于则向左查
                right=mid-1;
            }else if(arr[mid]<key){//小于则向右查
                left=mid+1;
            } else{//等于则返回索引
                return mid;
            }
        }
        return -1;//未查到返回-1
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 使用递归的情况

/**
     * @param arr：有序的线性查找表
     * @param low：左边索引
     * @param height：右边索引
     * @param key：待查找的关键字
     * @return：关键字的索引
     */
    public static int insertionSearch(int[] arr,int low,int height,int key) {
        int left=low;
        int right=height;
        int mid=left+((key-arr[left])/(arr[right]-arr[left]))*(right-left);
        if(left<=right){//递归退出条件
            if(arr[mid]>key){//大于则向左递归
                return insertionSearch(arr,low,mid-1,key);
            }else if(arr[mid]<key){//小于则向右递归
                return insertionSearch(arr,mid+1,height,key);
            } else{//等于则返回索引
                return mid;
            }
        }
        return -1;未查到返回-1
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.4， 斐波那契查（fibonacciSearch）

预备知识

• 在介绍斐波那契查找算法之前，我们先介绍一下这个概念——黄金分割比例
• 黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为0.618。
• 斐波那契数列：从第三个数开始，后边每一个数都是前两个数的和
• 例如：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….
• 菲波那切数列与黄金分割比例的关系：我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，因此斐波那契数列也被称为黄金分割数列
• 我们把斐波那契数列的这个特性运用到到查找技术中，就是所谓的斐波那契查找算法

类型

• 有序查找
• 查找表为线性表，有序

算法描述

• 斐波那契查找也是二分查找的一种优化
• 斐波那契查找改变了二分查找中原有的中值mid 的求解方式，其 mid不再代表中值，而是代表了黄金分割点
• mid的计算公式：mid=low+F[k-1]-1
• 斐波那契查找，以黄金分割点来分割数组
• 对F[k]-1的理解
  由于斐波那契数列的性质：F[k]=F[k-1]+F[k-2]，可以得到F[k]-1=F[k-1]-1+F[k-2]-1+1,该式说明，如果表的长度为F[k]-1，就可以将表分成F[k-1]-1和F[k-2]-1两段，其中分割点为：mid
  
• 算法实现前提：填充待查找的数列
  首先确定斐波那契数列：根据待查找表的长度来确定，斐波那契数列最后一项的大小与表的长度的关系：Fib[k]-1=arr.length

假如待查找表为一个数组：
arr[]={0,1,2,3,4,5,6,7,8,9}
表的长度为：10

斐波那契数列：Fib={1,1,2,3,5,8,13}

表的长度为10，在在Fib中找不到为11的项。

我们怎么实现：Fib[k]-1=arr.length哪？
	如果我们选择Fib=Fib={1,1,2,3,5,8}，显然我们要删除部分数据，不可取
	
	于是我们就只能选择Fib={1,1,2,3,5,8,13}，此时要想斐波那契数列
	最后一项的大小与表的长度有以下关系：Fib[k]-1=arr.length，我
	们就只能扩充表，由于表还需要有序，因此我们使用表的最后一项来
	填充即可。

注意：如果表的长度值和斐波那契数列中的某一项刚好满足：Fib[k]-1=arr.length，
此时我们就无需填充
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 算法实现步骤：
  （1）如果mid与给定关键字相同，则查找成功，返回在表中的位置；
  （2）如果mid比给定关键字小，向右查找并减小2个斐波那契区间；
  （3）如果mid比给定关键字大，向左查找并减小1个斐波那契区间；
  （4）重复过程，直到找到关键字（成功）或区间为空集（失败）

Java代码实现

 /**
     * 构建长度为20的斐波那契数列：
     * @return
     */
    public static int[] fib(){
        int[] Fib=new int[20];
        Fib[0]=1;
        Fib[1]=1;
        for(int i=2;i<20;i++){
            Fib[i]=Fib[i-1]+Fib[i-2];
        }
        return Fib;
    }

    /**
     * 斐波那契查找：
     * @return：查找到返回下标（非负），未查找到返回-1
     */
    public static int fibinacciSearch(int[] arr,int key){
        int low=0;//最小下标
        int height=arr.length-1;//最大下标
        int[] Fib=fib();
        int k=0;//记录Fib数列的下标值
        while(arr.length>Fib[k]-1){//计算最大下标对应的Fib数列位置
            k++;
        }
        //不满足条件：arr.length=Fib[k]-1时，扩充数组
        int [] temp= Arrays.copyOf(arr,Fib[k]);
        for(int i=arr.length;i<Fib[k];i++){//使用数组的最大值填充，保证有序
            temp[i]=arr[height];
        }

        //开始查找
        while(low<=height){
            int mid=low+Fib[k]-1;//当前分割下标
            if(key<temp[mid]){//向左查找
                height=mid-1;
                k=k-1;
            }else if(key>temp[mid]){//向右查找
                low=mid+1;
                k=k-2;
            }else {//查找到
                if(mid<=height){
                    return mid;//在未扩充区域查找到
                }else {
                    return height;//在扩充区域查找到
                }
            }
        }
        return -1;//未查找到
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51