栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java算法实现:四大查找算法

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java算法实现:四大查找算法

文章目录
  • 一、顺序查找算法
    • 1.1、算法介绍
    • 1.2、算法实现
  • 二、二分查找算法
    • 2.1、算法介绍
    • 2.2、算法实现
    • 2.3、优化
  • 三、插值查找算法
    • 3.1、算法介绍
    • 3.2、算法实现
  • 四、斐波那契(黄金分割法)查找算法
    • 4.1、简介
    • 4.2、算法实现


一、顺序查找算法 1.1、算法介绍

顺序查找(Order Search)也称为线形查找

  • 从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值num相比较,若相等则表示查找成功
  • 若扫描结束仍没有找到关键字等于num的结点,表示查找失败
  • 这种查找方式效率可能并不是最好的,但是确实最容易理解和实现的。

1.2、算法实现
public static int orderSearch(int[] arr, int num) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == num) {
            return i;
        }
    }
    return -1;
}

二、二分查找算法 2.1、算法介绍

二分查找(Binary Search)也称折半查找,它是一种效率较高的查找方法,但二分查找要求 线性表必须采用顺序存储结构 ,并且表中元素按关键字有序排列。

  • 首先确定该数组的中间下标:mid = (left + right) / 2
  • 让 arr[mid] 和要和查找的元素比较,如果要查找的元素更大,说明应该向右查找,反之向左
  • 将左(右)边当成一个新数组,重复第一第二步,即进行递归
  • 找到了就结束递归,或者遍历完了数组也没找到,也结束递归

2.2、算法实现
public static int binarySearch(int[] arr, int num) {
    return binarySearch(arr, 0, arr.length - 1, num);
}

public static int binarySearch(int[] arr, int left, int right, int num) {
    int mid = (left + right) / 2;
	
    // 当 left > right 时说明已递归完整个数组,但是没有找到
    if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
        return -1;
    }
	
	// 如果值小于中间值
    if (num < arr[mid]) {   	 // 往左边递归找
        return binarySearch(arr, left, mid - 1, num);
    // 如果值大于中间值
    } else if (num > arr[mid]) {  // 往右边递归找
        return binarySearch(arr, mid + 1, right, num);
    } else {
    	// 找到!!!!
        return mid;
    }
}

2.3、优化

当一个有序数组中有多个相同的值时,将所有的数值下标都找到:{1, 2, 2, 2, 7, 8, 9}

public static List binarySearch(int[] arr, int left, int right, int num) {
    List list = new ArrayList<>();
    int mid = (left + right) / 2;

    // 当 left > right 时说明已递归完整个数组,但是没有找到
    if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
        list.add(-1);
        return list;
    }

    if (num > arr[mid]) {         // 向右递归
        return binarySearch(arr, mid + 1, right, num);
    } else if (num < arr[mid]) {  // 向左递归
        return binarySearch(arr, left, mid - 1, num);
    } else {
        list.add(mid);

        // 向左边查找是否有相同的值
        int leftTemp = mid - 1;
        while (leftTemp >= 0 && arr[leftTemp] == num) {
            list.add(leftTemp);
            leftTemp--;
        }

        // 向右边查找是否有相同的值
        int rightTemp = mid + 1;
        while (rightTemp <= arr.length - 1 && arr[rightTemp] == num) {
            list.add(rightTemp);
            rightTemp++;
        }
    }
    return list;
}

// [3,2,1]

三、插值查找算法 3.1、算法介绍

插值查找(Insert Value Search)是二分查找的一种改良

主要是改良了算法计算mid的值

mid = left + (num - arr[left]) / (arr[right] - arr[left]) * (right - left)
  • 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快
  • 关键字分布不均匀的情况下,该方法不一定比二分查找要好。


3.2、算法实现
public static int insertValueSearch(int[] arr, int num) {
    return insertValueSearch(arr, 0, arr.length - 1, num);
}

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

四、斐波那契(黄金分割法)查找算法 4.1、简介

斐波那契查找(Fibonacci Search)又叫黄金分割查找,斐波那契查找和二分查找、插值查找也类似,数组也要是有序的。

不同之处还是mid的计算方法,mid不再是中间或者插值得到,而是位于黄金分割点的附近:mid = left + f(k-1) - 1。要使用斐波那契查找,就要先构建一个斐波那契数列,斐波那契数列的长度就和原始数组保持一致即可,主要是用来获取中间索引mid。

  • 斐波那契数列: {1,1,2,3,5,8,13,21,34,55} 相邻两个数的比例无限接近为 0.618
  • 由斐波那契数列 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
  • 但顺序表长度 n 不一定为 F[K]-1,所以需要将原来的顺序长度 n 增加至 F[k]-1

4.2、算法实现
// 获取斐波那契数列 {1,1,2,3,5,8,13,21,34,55 ....}
public static int[] fib(int length) {
    int[] fibArr = new int[length];
    fibArr[0] = 1;
    fibArr[1] = 1;
    for (int i = 2; i < length; i++) {
        fibArr[i] = fibArr[i - 1] + fibArr[i - 2];
    }
    return fibArr;
}

//斐波那契查找算法
public static int fibonacciSearch(int[] arr, int num) {
    int[] f = fib(arr.length);                  //获取斐波那契的数组
    int left = 0;                               //原始数组左边的下标
    int right = arr.length - 1;                 //原始数组右边的下标
    int k = 0;                                  //斐波那契数组的下标
    while (f[k] - 1 < right) {                  //指向数组的最后索引
        k++;
    }

    //由于f(k)不是步长为1的递增数列,所以可能出现f(k) - 1的值大于原始数组最后一个索引的情况
    //比如原始数组最大索引为4,那么此时f(k)就等于5,所以要构造一个新数组,不够的部分会用0填充
    //如果多余部分用0填充可能会造成查找失败,因此,需要将0的部分填充为原来数组中的最后一个元素
    int[] temp = Arrays.copyOf(arr, f[k]);
    for (int i = right + 1; i < temp.length; i++) {
        temp[i] = arr[right];
    }


    while (left <= right) {                     //循环查找
        int mid = left + f[k - 1] - 1;          //获取mid
        if (num < temp[mid]) {                  //往左查找
            right = mid - 1;
            k -= 1;
        } else if (num > temp[mid]) {           //往右查找
            left = mid + 1;
            k -= 2;
        } else {
            return mid <= right ? mid : right;  //返回下标
        }
    }
    return -1;
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948957.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号