查找算法

在上边文章总结了常见的排序算法,本文接着上篇内容来介绍总结常见的查找算法。

  • 线性查找
  • 二分查找BinarySearch
  • 插值查找
  • 斐波那契(黄金分割)查询

线性查找

遍历待查找的数列,逐个比较,直到匹配项介绍。

public static int seqSearch(int[] array, int findVal) {
    int length = array.length;
    for(int i = 0; i < length; i ++) {
        if(findVal == array[i]) {
            return i;
        }
    }
    return -1;
}

二分查找Binary Search

二分查找也称折半查找,搜索的特点是:每经历一次比较,都是搜索范围缩小一半。
查找思路:

  • 从数列的中间开始查找
  • 如果中间元素正好匹配,则查找过程结束
  • 如果目标元素大于中间元素,则接着从大于中间元素那一半查找
  • 如果目标元素小于中间元素,则接着从小于中间元素那一半查找

中值公式:
BinarySearch

具体实现代码:

public class BinarySearch {
    public static void main(String[] args) {
        int [] array = {1, 10, 20, 30, 40, 50, 50, 50, 60, 70, 80, 90};
        // 查找匹配的位置
        int index = binarySearch(array, 0, array.length - 1, 90);
        if(-1 == index) {
            System.err.println("没有找到");
        } else {
            System.out.println("找到该值,位置在:" + index);
        }
        
        //查找所有匹配的位置
        List<Integer> results = binarySearch2(array, 0, array.length - 1, 50);
        if(results.isEmpty()) {
            System.err.println("没有找到");
        } else {
            System.out.println("找到,位置在:" + Arrays.toString(results.toArray()));
        }
    }

    // 二分查找
    public static int binarySearch(int[] array, int left, int right, int findValue) {
        System.out.printf("查找中...%d~%d\n", left, right);
        // 没有找到
        if(left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midValue = array[mid];
        // 中间值大于待查找值,往左边进行查找
        if(midValue > findValue) {
            return binarySearch(array, left, mid - 1, findValue);
        }
        // 中间值小于待查找值,往右边进行查找
        else if(midValue < findValue) {
            return binarySearch(array, mid + 1, right, findValue);
        }
        // 找到
        else {
            return mid;
        }
    }
    
    // 二分查找(获取所有匹配项)
    public static List<Integer> binarySearch2(int [] array, int left, int right, int findValue) {
        if(left > right) {
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        int midValue = array[mid];
        if(midValue > findValue) {
            return binarySearch2(array, left, mid - 1, findValue);
        }
        else if(midValue < findValue) {
            return binarySearch2(array, mid + 1, right, findValue);
        }
        else {
            List<Integer> results = new ArrayList<>();
            // 向左查找
            int tmp = mid - 1;
            while(array[tmp] == findValue) {
                results.add(tmp);
                tmp--;
            }
            results.add(mid);
            // 向右查找
            tmp = mid + 1;
            while(array[tmp] == findValue) {
                results.add(tmp);
                tmp++;
            }
            return results;
        }
    }
}

插值查找

插值查找是在二分查找的基础上进行改进,使开始比较的middle自适应。
其中值计算公式:
InsertValueSearch
该算法代码:

// 插值查找
// mid = low + (high - low) * (key - a[low]) / (a[high] - a[low])
public static int insertValueSearch(int [] array, int low, int high, int key) {
    if(low > high) {
        return -1;
    }
    int mid = low + (high - low) * (key - array[low]) / (array[high] - array[low]);
    if(array[mid] < key) {
        return insertValueSearch(array, mid + 1, high, key);
    }
    else if(array[mid] > key) {
        return insertValueSearch(array, low, mid - 1, key);
    }
    return mid;
}

插值查找与二分查找对比:

  1. 对于数据量较大,关键字分布比较均匀的查找列表来说,插值查找速度会比较快。
  2. 对于关键字分布不均匀的,插值查找不一定比折半查找好。

斐波那契(黄金分割)查找

斐波那契查找原理:
该查找原理与二分查找插值查找类似,仅仅改变中间节点middle位置,middle位置不再是中间或插值得到,而是位于黄金分割点附近,即mid = low + F(k - 1) - 1(F,斐波那契数列)。

FibonacciSearch.png

F(k-1)-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]-1F[k-2]-1的两段,即中间位置为:mid=low+F[k-1]-1
  • 类似的每个字段也可以用相同的方式进行分割。
  • 可能顺序表长度n不一定等于F[k]-1,需要将原来的顺序表长度n增加至F[k]-1。(k值只要使得F[k]-1大于或等于n)。
public class FibonacciSearch {
    public static int maxSize = 20;
    
    public static void main(String[] args) {
        // System.out.println(Arrays.toString(fibonacci()));
        int[] array = {1, 8, 10, 89, 1000, 1234};
        int index = fibonacciSearch(array, 1);
        if(-1 == index) {
            System.err.println("没有找到");
        } else {
            System.out.println("找到,位置:" + index);
        }
    }
    
    // 斐波那契数列数组
    public static int[] fibonacci() {
        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 static int fibonacciSearch(int[] array, int key) {
        int length = array.length;
        int low = 0;
        int high = length - 1;
        int k = 0;    // 斐波那契分割数的索引
        int mid = 0;
        int[] f = fibonacci();
        // 找到有序表元素个数在斐波那契数列中最接近的最大数列值
        while(high > (f[k] - 1)) {
            k++;
        }
        // 补齐有序表
        int [] tmpArray = Arrays.copyOf(array, f[k]);
        for(int i = length; i < tmpArray.length; i++) {
            tmpArray[i] = array[high];
        }
        while(low <= high) {
            mid = low + f[k - 1] - 1;
            // 查找值小于中值,在小的那一部分继续查找
            if(key < tmpArray[mid]) {
                high = mid - 1;
                k--;
            }
            // 查找值大于中值,在大的那一部分继续查找
            else if(key > tmpArray[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                // 可能存在补齐列表
                if(mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

标签: none

已有 2 条评论

  1. yd yd

    您好,我刚刚搭建了一个博客系统,阅读剩余部分 点击无法使用,想请教一下您。

    1. 也是用typecho吗?如果是的话,可以直接插入内容:。
      或者点击编辑器上面的工具按钮:摘要分割线 , 快捷键是:Ctrl + M。

添加新评论