程序员经验分享-hwhale

【数据结构与算法】（Java）二分法查找，插值查找，斐波那契查找，哈希表应用场景：员工信息管理在内存中

2023-05-16

查找算法

有序表查找

二分法查找

package dataStructure;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
	public static void main(String[] args) {
		int[] arr = {20,70,80,110,121,134};
		int index = binarySearch1(arr,134);
		System.out.println(index);
		//-----------------------------------测试加强版方法
//		int[] arr = {20,80,70,100,100,100,101,102,103,104};
//		List<Integer> list = binarySearch(arr,100,0,arr.length-1);
//		System.out.println(list);
	}
	//方式一：普通循环法
	public static int binarySearch1(int[] arr,int val) {
		int left = 0;
		int right = arr.length-1;
		while(true) {
			int mid = (left + right) / 2;
			
			if(arr[mid] == val) {
				return mid;
			}else if(arr[mid] > val) {
				right = mid - 1;
			}else {
				left = mid + 1;
			}
			if(left > right) {
				return -1;
			}
		}
	}
	//方式二：递归法
	public static int binarySearch2(int[] arr,int val,int left,int right) {
		//当left > right时，说明数组已经遍历完都找不到
		if(left > right) {
			return -1;
		}
		int mid = (left + right) / 2;
		int midVal = arr[mid];
		
		if(midVal > val) {//说明需要查找的元素不在右边，则向左递归
			return binarySearch2(arr,val,left,mid-1);
		}else if(midVal < val) {//说明需要查找的元素不在右边，则向左递归
			return binarySearch2(arr,val,mid+1,right);
		}else {
			return mid;
		}
	}
	//方式三：完善二分法查找功能。即当数组中有多个相同值时，要求返回每一个的下标
	public static List<Integer> binarySearch(int[] arr,int val,int left,int right){
		if(left > right) {
			return new ArrayList();
		}
		int mid = (left+right) / 2;
		int midVal = arr[mid];
		if(midVal > val) {
			return binarySearch(arr,val,left,mid-1);
		}else if(midVal < val) {
			return binarySearch(arr,val,mid+1,right);
		}else {
			/**
			 * 因为传入的数组是有序的，那么说明相同的元素的索引肯定是相邻的
			 * 集合List是存放有序且不重复的数据
			 * list用于存放查找到的下标
			 * */
			ArrayList<Integer> list = new ArrayList<>();
			//先向mid左边一一查找，做对比
			int temp1 = mid-1;//记录mid前一个索引
			while(true) {
				if(temp1 < 0 || arr[temp1] != val) {
					break;
				}
				list.add(temp1--);
			}
			list.add(mid);//将mid也添加进集合list
			//再向mid右边一一查找遍历，作对比
			int temp2 = mid + 1;
			while(true) {
				if(temp2 > right || arr[temp2] != val) {
					break;
				}
				list.add(temp2++);
			}
			return list;
		}
	}
}

插值查找

当我们需要查找的数组中数组比较连续且有序的数据时，采用插值查找更能提高查找效率。可以做到自适应计算mid.例如:arr[] = {1,2,3,…1000};这样的数组

适合使用的场景：

​ 1.对于数据量比较大，关键字分布比较均匀的查找表来说，插值查找的数比二分查找要快

​ 2.关键字分布不均匀的情况下，不一定比二分法要好

在二分法中：
m i d = ( l e f t + r i g h t ) / 2 = l e f t + 1 / 2 ( r i g h t − l e f t ) mid = (left+right)/2=left + 1/2(right-left) mid=(left+right)/2=left+1/2(right−left)
将上面公式转换成：
m i d = l e f t + [ ( f i n d V a l u e − a r r [ l e f t ] ) / ( a r r [ r i g h t ] − a r r [ l e f t ] ) ] ∗ ( r i g h t − l e f t ) mid = left + [(findValue-arr[left])/(arr[right]-arr[left])]*(right-left) mid=left+[(findValue−arr[left])/(arr[right]−arr[left])]∗(right−left)
例：

package dataStructure;
public class InsertValueSearch {
	private static int count=0;
	public static void main(String[] args) {
		//创建一个1~100的数组
		int[] arr = new int[100];
		for(int i=0;i < 100;i++) {
			arr[i] = i+1;
		}
		int index = insertSearch(arr,33,0,arr.length-1);
		System.out.println("查找了"+count+"次");
		System.out.println("index="+index);
	}
	public static int insertSearch(int[] arr,int findValue,int left,int right) {
		count++;
		//检验合法性
		if(left > right || findValue < arr[0] || findValue > arr[arr.length-1]) {
			return -1;
		}
		int mid = left + (right - left)*(findValue - arr[left])/(arr[right] - arr[left]);
		if(findValue > arr[mid]) {//向右查找
			return insertSearch(arr,findValue,mid+1,right);
		}else if(findValue < arr[mid]) {//向左查找
			return insertSearch(arr,findValue,left,mid-1);
		}else {
			return mid;
		}
	}

}

斐波那契查找

因为斐波那契数列相邻两个数的比例，无限接近黄金分割比值0.618.所以又称为黄金分割法

理解mid = low + F(k-1) -1
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PLGVQG5x-1652774515721)(D:\Desktop\Java\imag\斐波那契查找.png)]

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)但顺序表长度n不一 定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[K]-1恰好大于或等于n即可，由以下代码得到顺序表长度增加后，新增的位置(从n+ 1到F[k]-1位置)，都赋为n位置的值即可。
whle(n>fib(k)-1) k++;

代码：

package dataStructure;

import java.util.Arrays;

public class Test {
    static int maxSize = 20;
    public static void main(String[] args) {
        int[] arr = {0,1,16,24,35,47,59,62,73,88,99};
        System.out.println("index="+ fibonacciSearch(arr,99));

    }
    //获取斐波拉契数列
   public static int[] fib(){
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
       for (int i = 2; i < f.length; i++) {
           f[i] = f[i - 1] + f[i - 2];
       }
       return f;
   }
   //算法
    public static int fibonacciSearch(int[] arr,int key){
        int left = 0;
        int right = arr.length - 1;
        int k = 0;
        int mid = 0;
        int[] f = fib();//获得Fibonacci数列
        while(right > f[k] - 1){//获得斐波那契分割数值的下标
            k++;
        }
        //因为f[k] 的值可能会大于arr的长度，所以需要一个长度为f[k]的数组
        int[] temp = Arrays.copyOf(arr,f[k]);//将数组arr复制给temp去，temp的长度大于arr的
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];//使用arr数组的最后一个元素来填充temp的后面全为0的元素
        }
        //寻找key
        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{//找到
                if( mid <= right){
                    return mid;
                }else{
                    return right;
                }
            }
        }
        //元素不存在返回-1
        return -1;
    }
}

哈希表

哈希表可以看成是以个缓存层，功能没有Redis强大。减少对数据库的操作。
散列技术：

散列技术既是一种存储方法，也是一种查找方法
散列技术最适合的求解问题：查找与给定值相等的记录

散列表内存结构图示：
在这里插入图片描述

使用场景：一个上机题
有一个公司,当有新的员工来报道时，要求将该员工的信息加入(id,性别,年龄,住址.),当输入该员工的id时,要求查找到该员工的所有信息要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

package map;
import java.util.Scanner;
public class MyHashList {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(10);//创建了有10条链表的哈希表
        Scanner scanner = new Scanner(System.in);
        String in = "";
        while(true){
            System.out.println("put:添加员工信息！");
            System.out.println("dis:遍历员工信息！");
            System.out.println("fin:查找员工信息！");
            System.out.println("del:删除员工信息！");
            System.out.println("exit:退出系统！！");
            in = scanner.next();
            switch(in){
                case "put":
                    System.out.println("员工id：");
                    int id = scanner.nextInt();
                    System.out.println("员工姓名：");
                    String name = scanner.next();
                    hashTable.put(new Node(id,name));
                    break;
                case "dis":
                    System.out.println("哈希表的信息为：");
                    hashTable.getTable();
                    break;
                case "fin":
                    System.out.println("请输入需要查找的员工id：");
                    int id1 = scanner.nextInt();
                    hashTable.search(id1);
                    break;
                case "del":
                    System.out.println("请输入想要删除的员工id：");
                    int id2 = scanner.nextInt();
                    hashTable.remove(id2);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }
}
//------------------------------------------------------------------------哈希表类
//管理多条链表
class HashTable{
    private NodeLinkList[] nodeLinkListArray;//链表类型的数组，这个数组里面可存放多条链表
    private int size;
    public HashTable(int size){//size指哈希数组长度
        this.size = size;
        //初始化哈希数组
        nodeLinkListArray = new NodeLinkList[size];
        //分别初始化每一条链表
        for (int i = 0; i < size; i++) {
            nodeLinkListArray[i] = new NodeLinkList();
        }

    }
    //散列函数，这里采用取模留于法
    //用于寻找结点在哈希数组中的链表位置
    public int hashFunction(int id){
        return id % size;
    }
    //添加员工
    public void put(Node node){
        //根据员工的id，获取添加的目的链表数组下标
        int no = hashFunction(node.getId());
        //添加到相应的链表中
        nodeLinkListArray[no].add(node);
    }
    //遍历HashTable,即所有的链表
    public void getTable(){
        for (int i = 0; i < size; i++) {
            nodeLinkListArray[i].list(i);
        }
    }

    //根据id查找哈希表中的员工信息
    public void search(int id){
        int no = hashFunction(id);
        Node node = nodeLinkListArray[no].find(id);
        if(node != null){
            System.out.println("需要查找的对应id的员工信息为:");
            System.out.println("id:"+node.getId());
            System.out.println("name:"+node.getName());
        }else{
            System.out.printf("id输入有误，哈希表中没有%d对应的员工信息,请仔细检查核对id信息",id);
        }
    }

    //根据id删除哈希表中某一链表上对应的id结点
    public void remove(int id){
        int no = hashFunction(id);
        nodeLinkListArray[no].delete(id);
    }
}
//------------------------------------------------------------------------链表类
class NodeLinkList{
    //声明一个空的头结点
    private Node head;
    /**
     * 添加员工信息结点
     * 假设id是自增长的
     * */
    public void add(Node node){
        //如果链表为空
        if(head == null){
            head = node;
            return;
        }
        Node cur = head;//遍历的当前结点
        //尾插法
        while(true){
            if(cur.getNext() == null){//说明已经找到最后的结点
                break;
            }
            cur = cur.getNext();
        }
        cur.setNext(node);//找到的当前结点指向新插入的结点
    }

    //遍历链表员工信息
    public void list(int no){
        System.out.print("第"+no+"条链表信息为：");
        if(head == null){
            System.out.print(".......\n");
            return;
        }
        Node cur = head;
        while(true){
            System.out.printf("-->id=%d  name=%s\t",cur.getId(),cur.getName());
            if(cur.getNext() == null){//链表中结点已经遍历完
                break;
            }
            cur = cur.getNext();
        }
        System.out.println();
    }

    //查找链表结点
    public Node find(int id){
        Node cur = head;
        while(true) {
            if (cur.getId() == id) {
                break;
            }
            if(cur.getNext() == null){
                cur = null;//如果比遍历完这条链表还没有找到，则置为空，说明没有找到
                break;
            }
            cur = cur.getNext();
        }
        return cur;
    }

    //删除结点
    public void delete(int id){
        if(head == null){
            System.out.println("此链表没有数据");
            return;
        }
        Node cur = head;
        boolean flag = false;
        while(true){
            if(cur.getNext() == null){//没找到
                break;
            }
            if(cur.getNext().getId() == id){//找到了
                flag = true;
                break;
            }
            cur = cur.getNext();
        }
        if(flag){
            cur.setNext(cur.getNext().getNext());
        }else {
            return;
        }
    }
}
//------------------------------------------------------------------------链表结点类
class Node{
    private int id;
    private String name;
    private Node next;//next指针默认为空
    public Node(){

    }
    public Node(int id,String name){
        super();
        this.id = id;
        this.name = name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setId(int id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }

    public int getId() {
        return id;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【数据结构与算法】（Java）二分法查找，插值查找，斐波那契查找，哈希表应用场景：员工信息管理在内存中 的相关文章

  • STM32 - 用户自定义通讯协议

    一 自定义协议 帧头1 xff1a 0x5A 帧头1 xff1a 0xA5 命令类型 xff1a 0x01 ADC 读取电压 0x02 外部flash写入 0x03 外部flash 读取 0x04 内部flash 写入 0x05 内部fla

  • 串口通信介绍

    文章目录 1 串口通信简介 xff08 DB9接口讲解 xff09 2 串口通信基本原理 xff08 1 xff09 串口通信连线 xff08 2 xff09 串口通信时序 1 波特率 2 起始位 3 数据位 4 奇偶校验位 5 停止位 3

  • curl 命令详解（超详细）

    GET 请求 GET 方法是在 curl 中发出请求的默认方法 xff0c 因此不必指定任何参数 eg curl https blog ucwords com o 保存响应到文件中 curl o response tex https blo

  • Matlab 命令行显示循环显示进度条

    提示 xff1a 文章写完后 xff0c 目录可以自动生成 xff0c 如何生成可参考右边的帮助文档 目录 前言一 代码二 简单说明三 测试总结 前言 闲来无事 xff0c 在用Matlab跑循环比较长的时候 xff0c 时间长 xff0c

  • Hikvison对接NVR实现WEB无插件开发包实现前端视频预览(html、vue、nginx代理)

    场景 Vue中预览HIKVSION海康威视的NVR 网络硬盘录像机 中多个通道 摄像机 的视频 xff1a Vue中预览HIKVSION海康威视的NVR 网络硬盘录像机 中多个通道 摄像机 的视频 霸道流氓气质的博客 CSDN博客 海康nv

  • C++ 为什么编写模板类时要把方法的实现写在头文件中，而不能像写普通类一样写在源文件中？

    1 回答标题的问题 这里说下我自己的理解 xff0c 如有不正确请各位大佬斧正 想要解决这个问题需要先了解C 43 43 代码的编译过程 C 43 43 将代码编译生成可执行文件的过程可以分为三步 xff1a 预编译 编译 链接 预编译时

  • 加速度计、陀螺仪工作原理

    加速度计 陀螺仪的工作原理 参考链接 xff1a https c miaowlabs com B07 html 陀螺仪 加速度计都是惯性测量元件的一种 而 MPU 6050 传感器的内部同时集成了陀螺仪和加速度传感器两种惯性测量元件 1 加

  • VsCode中运行C/C++

    VsCode中运行C C 43 43 1 插件 runCode2 配置环境 mingw64 1 插件 runCode 在 VsCode 中的扩展商店中 xff0c 下载插件 Code Runner 安装完成之后 xff0c 进行一些配置更改

  • 常见通信协议之UART、RS485

    UART 通用异步收发器一种通用的串行 异步通信总线 xff0c 该总线有两条数据线 xff0c 可以实现全双工的发送和接受并行通信和串行通信 总线传递数据的本质 高低电信号并行通信 一次性传输多个位 布线难度高 存在数据干扰串行通信 逐次

  • java的琐碎学习之串口通信与数据库与GUI

    RFID作业 xff0c 要求实现软硬结合 xff0c 全部使用自己的页面完成 xff1b 找了几个教程发现安卓我做不到 xff0c 就用了Java实现 xff1b 图书管理系统 可以通过写卡来绑定15693卡和书籍 xff0c 实现增删改

  • C++- #define 和 const 有什么区别？

    回答如下 xff1a 定义不同 xff1a define 是C 43 43 预处理器的指令 xff0c 用于定义宏 xff0c const是C 43 43 关键字 xff0c 用于定义常量 作用对象不同 xff1a define 定义的宏

  • HTTP协议：二.使用工具观察 HTTP 的请求和响应

    二 使用工具观察 HTTP 的请求和响应 1 HTTP 协议格式 HTTP 是一个文本格式的协议 可以通过 Chrome 开发者工具或者 Fiddler 抓包 分析HTTP 请求 响应的细节 2 抓包工具的下载和使用 直接去官网下载即可 f

  • Linux环境下的c语言编程

    vim编辑器编辑hello c vim编辑器中输入相应代码 编译 运行代码 运行结果 使用GDB函数调用 编译生成可执行文件 启动gdb 第十行设置断点并运行 gcc过程改为makefile管理 编写makefile文件 启动makefil

  • ubuntu下关于ssh远程和scp远程复制文件以及nfs搭建

    SSH远程 在Linux系统中 xff0c 通过客户端连接到远程服务器中 xff0c 方便代码地编写运行 xff0c ssh是一种安全协议 xff0c 主要用于给远程登录信息数据进行加密 1 安装ssh 2 启动ssh 3 创建要发送的文件

  • Linux环境下的多线程&多进程编程

    1 线程的创建与终止 创建一个 c文件 xff0c 使用vi编辑器进行多线程的创建 编译文件 在编译文件时会出现对 pthread create 未定义的引用 xff0c 这是由于pthread 库不是Linux系统默认的库 xff0c 连

  • 东北天坐标系转载体坐标系

    文章目录 1 基本概念1 1欧拉角1 2左乘右乘1 3东北天坐标系1 4载体坐标系1 5捷联惯性导航系统 2 通过ECEF转换到参考点附近的ENU坐标系上3 东北天坐标系到载体坐标系 1 基本概念 1 1欧拉角 欧拉旋转定理指出 xff1a

  • I2C驱动App

    1 查看eeprog c源代码 copyright C by 2009 Guangzhou FriendlyaRM in China email capbily 64 163 com website arm9 net include lt

  • Qt5.14.2 编程应用

    Qt5 14 2 编程应用 什么是Qt Qt 是一个跨平台的 C 43 43 图形用户界面库 xff0c 由挪威 TrollTech 公司于 1995 年底出品 xff0c 并于 2008年6月17日被NOKIA公司收购 xff0c 以增强

  • L298N电机驱动的使用

    L298N电机驱动的使用 前言一 介绍L298N模块简介接口介绍 二 使用步骤硬件连接软件部分1 声明部分2 代码部分 总结 前言 博主为某大学电气专业大学生 xff0c 以学习为目的写下该文 xff0c 内容主要为以51单片机为例简单介绍

  • Authorization头的作用

    Authorization头的主要用作http协议的认证 Authorization的作用是当客户端访问受口令保护时 xff0c 服务器端会发送401状态码和WWW Authenticate响应头 xff0c 要求客户机使用Authoriz

随机推荐

热门标签