【JAVA入门】Day23 - 查找算法

2024-08-21 16:36
文章标签 java 算法 入门 查找 day23

本文主要是介绍【JAVA入门】Day23 - 查找算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【JAVA入门】Day23 - 查找算法

文章目录

  • 【JAVA入门】Day23 - 查找算法
    • 一、基本查找
    • 二、二分查找 / 折半查找
    • 三、分块查找

        查找算法我们常用的有：

  • 基本查找
  • 二分查找 / 折半查找
  • 分块查找
  • 插值查找
  • 斐波那契查找
  • 树表查找
  • 哈希查找

        这里我们着重讲解前三种，其他查找方式除了树表查找，都是前三种的扩展。

一、基本查找

131 127 147 81 103 23 7 79

        在一堆数据中找出想要的数据，只需要将它们放入一个容器中，挨个遍历，直到找到想要的数据。

package BasciSeach;public class BasicSearchDemo1 {public static void main(String[] args) {//从0索引开始挨个往后查找//基本查找/顺序查找//数据：{131, 127, 147, 81, 103, 23, 7, 79}//需求：是否存在int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};int num = 18;boolean result = basicSearch(arr, num);System.out.println(result);}//参数：//一：数组//二：要查找的元素public static boolean basicSearch(int[] arr, int num) {//利用基本查找number是否在数组中存在for(int i = 0; i < arr.length; i++) {if(arr[i] == num){return true;}}return false;}
}

        利用基本查找，返回元素的索引（不考虑有无重复元素）。

package BasciSeach;public class BasicSearchDemo2 {public static void main(String[] args) {//从0索引开始挨个往后查找//基本查找/顺序查找//数据：{131, 127, 147, 81, 103, 23, 7, 79}//需求：返回索引int[] arr = {131, 127, 147, 81, 103, 23, 7, 79};int num = 7;int index = basicSearch(arr, num);if(index > 0) {System.out.println(index);}else{System.out.println("未找到元素");}}//参数：//一：数组//二：要查找的元素public static int basicSearch(int[] arr, int num) {//利用基本查找number是否在数组中存在for(int i = 0; i < arr.length; i++) {if(arr[i] == num){return i;}}return -1;}
}

        利用基本查找，返回元素的所有索引（考虑有重复元素）。

package BasciSeach;import java.util.ArrayList;public class BasicSearchDemo3 {public static void main(String[] args) {//利用基本查找，返回元素的索引（考虑有重复元素）//返回所有索引int[] arr = {131, 127, 147, 81, 103, 23, 7, 81};int num = 81;ArrayList<Integer> list = basicSearch(arr, num);System.out.print("[");for(int i = 0; i < list.size(); i++) {if(i < list.size() - 1) {System.out.print(list.get(i) + ", ");}else{System.out.print(list.get(i));}}System.out.print("]" + "\n");}//心得：//如果要返回多个数据的话，可以放入集合中public static ArrayList<Integer> basicSearch(int[] arr, int num) {ArrayList<Integer> list = new ArrayList<>();for(int i = 0 ; i < arr.length; i++) {if(arr[i] == num) {list.add(i);}}return list;}
}

二、二分查找 / 折半查找

        二分查找的数据有前提要求：数据必须是有序的。可以是从小到大排列，也可以是从大到小排列。
        二分查找的核心逻辑就是：每次排除一半的查找范围。因此查找效率比基本查找快很多。
        定义两个变量，min 指向 0 索引，max 指向 最大索引，（max + min）/ 2 可以得到中间的索引 mid。此时看该索引和要查找的数据大小关系，如果它比要查找的数据大，那么该数据所在的范围一定在 mid 索引的左半边，此时可以直接令 max = mid - 1，缩小索引范围；如果它比要查找的数据小，那么该数据所在范围一定在 mid 索引的右半边，此时可以直接令 min = mid + 1，缩小索引范围。重复此流程，直到max == min，此时就能找到所找的数据。如果要被查找的数据不存在，程序就会继续执行刚刚的逻辑，此时会发生 min > max，循环结束。

package BasciSeach;public class BinarySearchDemo1 {public static void main(String[] args) {//二分查找//{7, 23, 79, 81, 103, 127, 131, 147}int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};int number = 81;System.out.println(binarySearch(arr, number));}public static int binarySearch(int[] arr, int number) {//1.定义两个变量记录要查找的范围int min = 0;int max = arr.length - 1;//2.利用循环不断去找要查找的数据while(true) {if(min > max) {System.out.println("要查找的数据不存在!");return -1;}//3.找到min和max的中间位置int mid = (min + max) / 2;//4.拿着mid指向的元素跟要查找的元素进行比较//4.1number在mid左边//4.2number在mid右边//4.3number跟mid指向的元素一样if(arr[mid] > number) {max = mid - 1;}else if(arr[mid] < number) {min = mid + 1;}else if(arr[mid] == number) {return mid;}}}
}

        二分查找最大的优势就是能提高查找的效率，但是它要求数据必须是有序的。
        如果数据是乱序，先排序再使用二分查找得到的索引没有任何意义，只能知道这个数据是否存在。因为排序之后，数字的位置可能就发生变化了，新的索引没有参考价值。
        二分查找的效率其实可以进一步优化，将 mid 的计算方法改进，如下公式：

mid = min + (key - arr[min]) / (arr[max] - arr[min]) * (max - min);

        其中，key 是要查找的数据。此时这种查找方式就不叫二分查找了，而是叫做插值查找。
        还可以利用数学中的黄金分割点的概念进行改进：

mid = min + 黄金分割点左半边长度 - 1

        此时这种查找方法就不叫二分查找了，而是叫做斐波那契查找。

三、分块查找

        如果一组数据：块间有序，块内无序。这个时候我们可以应用分块查找。
        分块查找的原则在于：

  • 前一块中的最大数据，小于后一块中的所有数据（块内无序，块间有序）。
  • 块数数量一般等于数字的总个数开根号。比如：16个数字一般分为4块左右。

        块对象的定义一般如下所示：

class Block { 			//块int max;  			//块中的最大值int startIndex;		//起始索引int endIndex;		//结束索引
}

        将块对象放到一个数组中统一管理，这个数组一般叫做索引表。通过索引表，我们就能确定要查找的值存在于哪一块当中。
在这里插入图片描述
在这里插入图片描述
        比如上面的数据，我们可以轻易地发现，30就在第三个块当中（这个块级寻找的过程可以用基本查找或二分查找实现）。然后，我们再在块内使用遍历，就可以轻易找到要查找的数据30。

package BasciSeach;public class BlockedSearchDemo1 {public static void main(String[] args) {//1.创建数组blockArr存放每一个块对象的信息//2.先查找blockArr确定要查找的数据属于哪一块//3.再单独遍历这一块数据即可int[] arr = {16, 5, 9, 12, 21, 18,32, 23, 37, 26, 45, 34,50, 48, 61, 52 ,73, 66};//1.把数据分块//分几块：总数开根号 √18 = 4.24 块左右//每块里 18 / 4 = 4.5 个//创建三个块的对象Block b1 = new Block(21,0,5);Block b2 = new Block(32,6,11);Block b3 = new Block(50,12,17);//定义数组用来管理三个块的对象（索引表）Block[] blockArr = {b1, b2, b3};//定义一个变量用来记录要查找的元素int number = 32;//调用方法，传递索引表，数组，要查找的元素，返回要查找的数据索引int index = getIndex(blockArr, arr, number);//打印System.out.println(index);}//利用分块查找的原理，查询number的索引private static int getIndex(Block[] blockArr, int[] arr, int number) {//1.确定number在哪一块中，找到这一块的索引int indexBlock = findIndexBlock(blockArr, number);if(indexBlock == -1){//表示number过大，不在任何一块当中return -1;}//获取这一块的起始索引和结束索引int startIndex = blockArr[indexBlock].getStartIndex();int endIndex = blockArr[indexBlock].getEndIndex();//遍历这一部分的数组for(int i = startIndex; i <= endIndex; i++) {if(arr[i] == number) {return i;}}//遍历完整块都没找到，返回-1return -1;}//定义一个方法，用来确定number在哪一块中private static int findIndexBlock(Block[] blockArr, int number) {/*//创建三个块的对象Block b1 = new Block(21,0,5);Block b2 = new Block(32,6,11);Block b3 = new Block(50,12,17);*///从0索引开始遍历blockArr，如果number小于max，那么就表示number是在这一块当中的for (int i = 0; i < blockArr.length; i++) {if(number <= blockArr[i].getMax()) {return i;}}//当前数字过大，每一块中都找不到return -1;}
}class Block {private int max;private int startIndex;private int endIndex;public Block() {}public Block(int max, int startIndex, int endIndex) {this.max = max;this.startIndex = startIndex;this.endIndex = endIndex;}public int getMax() {return max;}public int getStartIndex() {return startIndex;}public int getEndIndex() {return endIndex;}
}

        如果数据本身没有规律。只需要保证数据间尚无交集，就可以完成分块。我们可以新增一个 min 变量，来记录每块中最小的值。
在这里插入图片描述
        如果查找的过程中还需要添加新数据呢？常见需求：在1~1000之间获取100个随机数，要求这些数据不重复，那就需要每添加一个数据就进行一次查找，查看该数据是否已经存在。这个时候就可以利用分块查找，把这100个数据分成10块，每一块规定要存储数据的范围。
在这里插入图片描述
        将要生成的数据放在相应块中，在各块中再进行遍历查找。这种查找方式作为分块查找的改进，被重新命名为哈希查找。
在这里插入图片描述

这篇关于【JAVA入门】Day23 - 查找算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1093691。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2