侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

查找算法

林贤钦
2020-06-21 / 0 评论 / 12 点赞 / 556 阅读 / 0 字
温馨提示:
本文最后更新于 2020-06-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

查找算法

查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找

1、顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。

代码实现

public static int seqSearch(int[]arr,int value){
    //线性查找就是逐一对比,发现相同值就返回下标
    for (int i = 0; i < arr.length; i++) {
        if (arr[i]==value){
            return i;
        }
    }
    return -1;
}

2、二分查找

元素必须是有序的,如果是无序的则要先进行排序操作。

基本思想:也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

代码实现

//TODO: 二分查找的前提是,该数组是有序的
private static int binarySearch(int[] arr,int left,int right,int value) {
    int mid =(left+right)/2;
    if (left>right){
        return -1;
    }
    if (value>arr[mid]){
        return binarySearch(arr,mid+1,right,value);
    }else if (value<arr[mid]){
        return binarySearch(arr,left,mid-1,value);
    }else if (value==arr[mid]){
        return mid;
    }
    return -1;
}

优化: 将所有相同的都返回

  • 思路:
  • 1.在找到mid索引值时,不要马上返回
  • 2.向mid索引值左边扫描,将满足的value的元素下标返加到ArrayList
  • 3.向mid索引值右边扫描,将满足的value的元素下标返加到ArrayList
  • 4.返回ArrayList
//TODO: 要求,将所有相同的都返回
private static List<Integer> binarySearch2(int[] arr, int left, int right, int value) {
    int mid =(left+right)/2;
    if (left>right){
        return new ArrayList<>();
    }
    if (value>arr[mid]){
        return binarySearch2(arr,mid+1,right,value);
    }else if (value<arr[mid]){
        return binarySearch2(arr,left,mid-1,value);
    }else if (value==arr[mid]){
        List<Integer> result = new ArrayList<>();
        result.add(mid);
        //向mid索引值左边扫描,将满足的value的元素下标返加到ArrayList
        int temp =mid-1;
        while (true){
            if (temp<0||arr[temp]!=value){
                break;
            }
            result.add(temp);
            temp --;
        }
        temp =mid+1;
        while (true){
            if (temp>arr.length-1||arr[temp]!=value){
                break;
            }
            result.add(temp);
            temp ++;
        }
        return result;
    }
    return null;
}

非递归版

public static int binarySearch(int[]arr,int target){
    int left =0;
    int right = arr.length-1;
    while(left<=right){
        int mid = (right+left)/2;
        if (arr[mid]==target){
            return mid;
        }else if (arr[mid]>target){
            right=mid-1;
        }else {
            left=mid+1;
        }
    }
    return -1;
}

3、插值查找

插值查找就是二分查找的升级版,在二分查找中,查找的数列如果是均匀分配的,查找边界值所需要的次数就比较多,而插值查找能够自适应查找,快速定位查找对象

适用于分布均匀的数据

基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。

  • 二分查找中查找点计算

    mid=(low+high)/2, 即mid=low+1/2*(high-low);

  • 插值查找的点改进为如下:

    mid=low+(key-a[low])/(a[high]-a[low])*(high-low),

代码实现

public static int insertValueSearch(int[] arr,int left,int right,int value){
    if (left>right){
        return -1;
    }
    int mid = left+((value-arr[left])/(arr[right]-arr[left]))*(right-left);
    if (value > arr[mid]){
        return  insertValueSearch(arr,mid+1,right,value);
    }else if (value<arr[mid]){
        return  insertValueSearch(arr,left,mid-1,value);
    }else {
        return mid;
    }
}

非递归版

public static int insertValueSearch(int[]arr,int target){
    int left =0;
    int right = arr.length-1;
    while(left<=right){
        int mid = left+((target-arr[left])/(arr[right]-arr[left]))*(right-left);;
        if (arr[mid]==target){
            return mid;
        }else if (arr[mid]>target){
            right=mid-1;
        }else {
            left=mid+1;
        }
    }
    return -1;
}

4、斐波那契(黄金分割法)查找算法

黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神奇的数字,会带来意向不大的效果。

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

基本思想:也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。

**斐波那契原理:**与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列)

  • 对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]-1和F[k-2]-1的两段,即如上图所示。从而中间位置为mid=low+F(k-1)-1
  • 类似的,每一子段也可以用相同的方式分割
  • 但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可。
public static int fibSearch(int[] a,int key){
    int low =0;
    int high =a.length-1;
    int k = 0;//表示斐波那契分割数值的下标
    int f[] = fib();//获取斐波那契数列
    int mid = 0;//存放mid值

    //获取到的斐波那契数列分割数值的下标
    while (high>f[k]-1){
        k++;
    }
    //因为f[k]的值可能大于a的长度,因此需要拷贝数组,超过的部分用0填充
    int[] temp = Arrays.copyOf(a,f[k]);
    //将填充的0,变为数组的最大值,即a[high]
    for (int i = high+1; i < temp.length; i++) {
        temp[i]=a[high];
    }
    System.out.println(Arrays.toString(temp));

    //使用循环找到key
    while (low<=high){
        System.out.println("hello~");
        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]的前面查找
            //下次循环mid = f[k-1-1]-1
            k--;//
        }else if (key > temp[mid]){
            low = mid+1;
            //下次循环mid = f[k-1-2]-1
            k -=2;
        }else {
            //确定返回下标
            if (mid<=high){
                return mid;
            }else {
                return high;
            }
        }
    }
    return -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;
}
12

评论区