记录生活中的点点滴滴

0%

查找

发表于 Valine：

这篇文章盘查找，下面会介绍四种简单的查找算法：

  1. 顺序查找
  2. 二分查找
  3. 插值查找
  4. 斐波那契查找

顺序查找

顺序查找应该是最简单的了，无论是否有序，我们按顺序查找就可以了，效率很低。

1
2
3
4
5
6
7
8
public static int search(int[] arr,int key){
    int len = arr.length;
    for (int i = 0; i < len; i++) {
        if(arr[i]==key)
            return i;
    }
    return -1;
}

二分查找

它要求数组必须是有序的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int search(int[] arr,int key){
    int left = 0;
    int right = arr.length-1;
    int mid;
    while (left<=right){
        mid = (left+right)>>1;//等价于(left+right)/2
        if(arr[mid]==key)
            return mid;
        else if(arr[mid]>key)
            right = mid-1;
        else
            left = mid+1;
    }
    return left;
}

也可用递归来实现，我们用的 while 循环。

插值查找

对于一个要查找的数我们不知道他大概在数组的什么位置的时候我们可以使用二分法进行查找。

但如果我们知道要查找的值大概在数组的最前面或最后面的时候使用二分法查找显然是不明智的。

之前二分法查找的时候我们比较的是中间值，mid = (left+right)/2;

插值查找的时候我们比较的不是中间值，是left+(key-arr[left])/(arr[right]-arr[left])*(right-left);

它和二分查找都差不多，无非是 mid 的值不一样，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int search(int[] arr,int key){
    //先判断
    if(key<arr[0] || key>arr[arr.length-1])
        return -1;
    int left = 0;
    int right = arr.length-1;
    int mid;
    while (left<=right){
        mid = left+(key-arr[left])/(arr[right]-arr[left])*(right-left);
        if(arr[mid]==key)
            return mid;
        else if(arr[mid]>key)
            right = mid-1;
        else
            left = mid+1;
    }
    return -1;
}

开始要先判断一下，不然如果我们的 key 值过小或过大可能会导致mid过大或过小，发生数组越界。

斐波那契查找

斐波那契数列 {1,1,2,3,5,8,13,21,34,55} 的两个相邻数的比例，无限接近黄金分割值0.618

斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid 不再是中间或插值得到，而是位于黄金分割点附近，即 mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示：

注意点：

  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=low+F(k-1)-1
  2. 类似的，每一段都可以这样分割
  3. 但是数组长度不一定等于 F[k]-1 ，所以我们需要把数组长度增加到 F[k]-1 。可以通过 while 循环来找到这个k值。

综上，我们自己再思考思考，其实也就前面多了找 k 值、扩数组使其满足条件这两步，接下来步骤和二分、插值都差不多，代码如下：

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
public static int search(int[] arr,int key){
    int len = arr.length;
    int f[] = fib();
    int k = 0;
    //获取到斐波那契分割数值的下标
    while (len > f[k]-1)
        k++;
    //复制数组
    int[] temp = Arrays.copyOf(arr,f[k]-1);
    //不足的用arr[len-1]填充
    for (int i = len; i < temp.length; i++) {
        temp[i] = arr[len-1];
    }
    int left = 0;
    int right = temp.length-1;
    int mid;
    while (left<=right){
        mid = left + f[k-1]-1;
        if(key<temp[mid]){//向前查找
            right = mid-1;
            k--;
        }else if(key>temp[mid]){//向后查找
            left = mid+1;
            k-=2;
        }else{//找到
            return mid>=len ? len-1 : mid;
        }
    }
    return -1;
}