java 二分法详解几种实现方法

2024-09-29 13:52:38

java 二分法详解几种方法

二分查找(java实现)

二分查找

算法思想：又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。

实现：

1.非递归代码

public static int biSearch(int []array,int a){
    int lo=0;
    int hi=array.length-1;
    int mid;
    while(lo<=hi){
      mid=(lo+hi)/2;
      if(array[mid]==a){
        return mid+1;
      }else if(array[mid]<a){
        lo=mid+1;
      }else{
        hi=mid-1;
      }
    }
    return -1;
  }

2.递归实现

public static int sort(int []array,int a,int lo,int hi){
    if(lo<=hi){
      int mid=(lo+hi)/2;
      if(a==array[mid]){
        return mid+1;
      }
      else if(a>array[mid]){
        return sort(array,a,mid+1,hi);
      }else{
        return sort(array,a,lo,mid-1);
      }
    }
    return -1;
  }

时间复杂度为 O(logN)

查找第一个元素出现的位置（元素允许重复）

public static int biSearch(int []array,int a){
    int n=array.length;
    int low=0;
    int hi=n-1;
    int mid=0;
    while(low<hi){
      mid=(low+hi)/2;
      if(array[mid]<a){
        low=mid+1;
      }else{
        hi=mid;
      }
    }
    if(array[low]!=a){
      return -1;
    }else{
      return low;
    }
  }

查询元素最后一次出现的位置

public static int biSearch(int []array,int a){
    int n=array.length;
    int low=0;
    int hi=n-1;
    int mid=0;
    while(low<hi){
      mid=(low+hi+1)/2;
      if(array[mid]<=a){
        low=mid;
      }else{
        hi=mid-1;
      }
    }

    if(array[low]!=a){
      return -1;
    }else{
      return hi;
    }
  }

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

Java二分法查找_动力节点Java学院整理

算法假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2. 开始令front=0(指向3),end=7(指向88),则mid=3(指向36).因为mid>x,故应在前半段中查找. 令新的end=mid-1=2,而front=0不变,则新的mid=1.此时x>mid,故确定应在后半段中查找. 令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a
Java使用二分法进行查找和排序的示例

实现二分法查找二分法查找,需要数组内是一个有序的序列二分查找比线性查找:数组的元素数越多,效率提高的越明显二分查找的效率表示:O(log2N) N在2的M次幂范围,那查找的次数最大就是M, log2N表示2的M次幂等于N, 省略常数,简写成O(logN) 如有一个200个元素的有序数组,那么二分查找的最大次数: 2^7=128, 2^8=256, 可以看出7次幂达不到200,8次幂包括, 所以最大查找次数就等于8 //循环,二分查找 static int binarySearch(int
Java JDK 二分法分析demo(推荐)

如下所示: public class Test { public static void main(String[] args) { Long[] arr = new Long[100000]; for(int i =0;i<100000;i++) { arr[i] = (long) i; } System.out.println(binarySearch(arr, 3L)); Comparable midVal = (Comparable) 2L;; System.out.println(mi
java 二分法算法的实例

java 二分法算法的实例 1.前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现.所以
java 中二分法查找的应用实例

java 中二分法查找的应用实例二分查找的前提是:数组有序注意:mid的动态变化,否则出错!!! 实例代码: public class BiSearch { public static void main(String[] args) { new BiSearch().biFind(new int []{1,2,3,4,5,6,7},3); } public void biFind(int arr[],int y){ int start=0; int end=arr.length-1; in
java 二分法详解几种实现方法

java 二分法详解几种方法二分查找(java实现) 二分查找算法思想:又叫折半查找,要求待查找的序列有序.每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程.直到查找到了为止,否则序列中没有待查的关键字. 实现: 1.非递归代码 public static int biSearch(int []array,int a){ int lo=0; int hi=array.length
Java线程池的几种实现方法和区别介绍实例详解

下面通过实例代码为大家介绍Java线程池的几种实现方法和区别: import java.text.DateFormat; import java.text.SimpleDateFormat; import java.util.ArrayList; import java.util.Date; import java.util.List; import java.util.Random; import java.util.concurrent.Callable; import java.util.
Java SHA-256加密的两种实现方法详解

本文实例讲述了Java SHA-256加密的两种实现方法.分享给大家供大家参考,具体如下: 最近在做注册的一个功能,密码要进行加密,一开始想用MD5加密,但是听说被破解了已经,于是想玩玩SHA-256加密.学习了下,总结两种方法供后面参考: 1.利用Apache的工具类实现加密: maven: <dependency> <groupId>commons-codec</groupId> <artifactId>commons-codec</artifac
9种Java单例模式详解（推荐）

单例模式的特点一个类只允许产生一个实例化对象. 单例类构造方法私有化,不允许外部创建对象. 单例类向外提供静态方法,调用方法返回内部创建的实例化对象. 懒汉式(线程不安全) 其主要表现在单例类在外部需要创建实例化对象时再进行实例化,进而达到Lazy Loading 的效果. 通过静态方法 getSingleton() 和private 权限构造方法为创建一个实例化对象提供唯一的途径. 不足:未考虑到多线程的情况下可能会存在多个访问者同时访问,发生构造出多个对象的问题,所以在多线程下不可用这种
Java中Thread类详解及常用的方法

目录一.Thread 的常见构造方法二.Thread 的常见属性三.创建线程四.中断线程五.线程等待六.获取线程引用七.线程休眠八.线程状态总结一.Thread 的常见构造方法方法说明 Thread() 创建线程对象 Thread(Runnable target) 使用 Runnable 对象创建线程对象 Thread(String name) 创建线程对象并命名 Thread(Runnable target,String name) 使用 Runnable 对象创建线程
Spring详解四种加载配置项的方法

目录 1.spring加载yml文件 2.spring 加载 properties 文件 3.spring加载系统磁盘(properties)文件 4.spring加载xml文件 5.Java基于InputStream读取properties配置文件本文默认 spring 版本是 spring5 1 spring 加载 yml 文件 2 spring 加载 properties 文件 3 spring 加载系统磁盘文件 4 spring 加载 xml 文件 5 Java 基于 InputS
mysql 5.7.20解压版安装方法步骤详解(两种方法)

我来讲解下window64位下MySQL的安装,MySQL是在5.7开始安装版就只有32位下载服务了,这里我讲解解压版的MySQL如何安装,在安装MySQL解压版时对于新手的小编来说也是头疼得很,各种问题各种来没有安装版的一键轻松搞定的方便,安装时需要注意三点:1.路径配置,2.安装时MySQL端口被占用这时需要关闭被占用端口,3.cmd必须是在管理员环境下设置MySQL信息. MySQL官网: https://www.mysql.com/downloads/ http://www.jb51.n
IOS中Json解析实例方法详解(四种方法)

作为一种轻量级的数据交换格式,json正在逐步取代xml,成为网络数据的通用格式. 有的json代码格式比较混乱,可以使用此"http://www.bejson.com/"网站来进行JSON格式化校验(点击打开链接).此网站不仅可以检测Json代码中的错误,而且可以以视图形式显示json中的数据内容,很是方便. 从IOS5开始,APPLE提供了对json的原生支持(NSJSONSerialization),但是为了兼容以前的iOS版本,可以使用第三方库来解析Json. 本文将介绍Tou
Java基础之详解HashSet的使用方法

Java HashSet HashSet 基于 HashMap 来实现的,是一个不允许有重复元素的集合. HashSet 允许有 null 值. HashSet 是无序的,即不会记录插入的顺序. HashSet 不是线程安全的, 如果多个线程尝试同时修改 HashSet,则最终结果是不确定的. 您必须在多线程访问时显式同步对 HashSet 的并发访问. HashSet 实现了 Set 接口. HashSet 中的元素实际上是对象,一些常见的基本类型可以使用它的包装类. 添加元素 HashSet
详解5种Java中常见限流算法

目录 01固定窗口 02滑动窗口 03漏桶算法 04令牌桶 05滑动日志 06分布式限流 07总结 1.瞬时流量过高,服务被压垮? 2.恶意用户高频光顾,导致服务器宕机? 3.消息消费过快,导致数据库压力过大,性能下降甚至崩溃? ...... 在高并发系统中,出于系统保护角度考虑,通常会对流量进行限流:不但在工作中要频繁使用,而且也是面试中的高频考点. 今天我们将图文并茂地对常见的限流算法分别进行介绍,通过各个算法的特点,给出限流算法选型的一些建议,并给出Java语言实现的代码示例. 01固定窗

java 二分法详解几种实现方法

相关推荐

随机推荐