【数据结构】查找算法

简介: 【数据结构】查找算法

一、线性查找

package work.rexhao.search;

public class SeqSearch {
   
   
    public static void main(String[] args) {
   
   
        int[] num = new int[]{
   
   12, 32, 45, 69, 83, 64, 23, 65, 10};
        System.out.println(seqSearch(num, 83));
        System.out.println(seqSearch(num, 99));

    }

    private static int seqSearch(int[] num, int i) {
   
   
        for (int j = 0; j < num.length; j++) {
   
   
            if (num[j] == i) {
   
   
                return j;
            }
        }
        return -1;
    }

}

二、二分查找

1、思路

  1. 确定该数组的中间的下标:mid = (left +right) / 2
  2. 然后让需要查找的数findVal和 arr[mid] 比较:
    1. findVal > arr[mid],说明你要查找的数在mid 的右边,因此需要递归的向右查找
    2. findVal < arr[mid],说明你要查找的数在mid 的左边,因此需要递归的向左查找
    3. findval == arr[mid],说明找到,就返回
  3. 什么时候我们需要结束递归?
    1. 找到就结束递归
    2. 递归完整个数组,仍然没有找到findVal,也需要结束递归(当left>right就要退出)

2、代码实现

package work.rexhao.search;

import java.util.Arrays;

/**
 * 二分查找
 *
 * @author 王铭颢
 * @Date 2022/7/3 22:54
 */
public class BinarySearch {
   
   
    public static void main(String[] args) {
   
   
        int[] num = new int[]{
   
   10, 12, 23, 32, 45, 64, 65, 69, 83};
        System.out.println(Arrays.toString(num));
        System.out.println(binarySearch(num, 69, 0, num.length - 1));
        System.out.println(binarySearch(num, 99, 0, num.length - 1));
    }

    public static int binarySearch(int[] num, int target, int left, int right) {
   
   
        if (left > right) {
   
   
            return -1;
        }
        if (num[(left + right) / 2] == target) {
   
   
            return (left + right) / 2;
        } else if (num[(left + right) / 2] > target) {
   
   
            return binarySearch(num, target, left, (left + right) / 2);
        } else {
   
   
            return binarySearch(num, target, (left + right) / 2 + 1, right);
        }
    }
}

三、差值查找

1、思路

插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找。

自适应mid算法:int mid = left + (right - left) * (target - num[left]) / (num[right] - num[left]);

对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快.

关键字分布不均匀的情况下,该方法不一定比折半查找要好

2、代码实现

package work.rexhao.search;

import java.util.Arrays;

/**
 * 差值查找
 *
 * @author 王铭颢
 * @Date 2022/7/4 10:54
 */
public class InsertValueSearch {
   
   
    public static void main(String[] args) {
   
   
        int[] num = new int[]{
   
   10, 12, 23, 32, 45, 64, 65, 69, 83};
        System.out.println(Arrays.toString(num));
        System.out.println(insertValueSearch(num, 69, 0, num.length - 1));
        System.out.println(insertValueSearch(num, 99, 0, num.length - 1));
    }

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

}

四、斐波那契查找

1、思路

mid 位于黄金分割点附近,即 mid-low+F(k-1)-1(F 代表斐波那契数列)

由斐波那契数列 F[k]=F[K-1]+F[k-2]的性质,可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1

(F[k-1]-1):左边的子序列
(F[k-2]-1):右边子序列
1:mid

每一子段也用相同的方式分割

顺序表长度n不一定刚好等于 F[k]-1,所以需要将原来的顺序表长度n增加至 F[k]-1

(为了保证数组有序,copyOf会在末尾生成0,用最后一位数来填充后面的0)

2、代码实现

package work.rexhao.search;

import java.util.Arrays;

/**
 * 斐波那契查找Demo
 *
 * @author 王铭颢
 * @Date 2022/7/4 22:36
 */
public class FibonacciSearch {
   
   
    public static void main(String[] args) {
   
   
        int[] num = new int[]{
   
   10, 12, 23, 32, 45, 64, 65, 69, 83};
        System.out.println(Arrays.toString(num));
        System.out.println(fibSearch(num, 69));
        System.out.println(fibSearch(num, 99));
    }

    /**
     * 生成斐波那契数列
     *
     * @param maxSize 元素最大个数
     * @return 斐波那契数组
     */
    public static int[] fib(int maxSize) {
   
   
        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;
    }

    /**
     * 斐波那契查找
     *
     * @return 索引值
     */
    public static int fibSearch(int[] num, int target) {
   
   
        // 一、生成斐波那契数列
        int[] f = fib(20);
        // k:斐波那契分隔值的下表
        int k = 0;

        // 二、扩充数列
        // 1.找到适合的fib[k]大小
        while (num.length - 1 > f[k]) k++;
        // 2.扩充并复制数组
        int[] temp = Arrays.copyOf(num, f[k]);
        // 3.为了保证数组有序,copyOf会在末尾生成0,用最后一位数来填充后面的0
        for (int i = num.length; i < temp.length; i++) {
   
   
            temp[i] = num[num.length - 1];
        }

        // 三、查找
        int mid = 0;
        int low = 0;
        int high = num.length - 1;
        while (low < high) {
   
   
            mid = low + f[k - 1] - 1;
            if (target > temp[mid]) {
   
   
                // 比中间大 --> 找右边
                low = mid + 1;
                k -= 2;
            } else if (target < temp[mid]) {
   
   
                // 比中间小 --> 找左边
                high = mid - 1;
                k -= 1;
            } else {
   
   
                // 找到了
                return mid;
            }

        }
        // 没找到
        return -1;
    }
}
目录
相关文章
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
76 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
90 0
|
11月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
420 1
|
12月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
632 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
203 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
318 25
|
8月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
298 23
|
11月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
195 33
|
9月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
263 3
|
11月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
229 19