java实现二分法的完整代码
作者:心所向在脚下 发布时间:2023-08-18 22:09:06
标签:java,二分法
二分法查找,顾名思义就是要将数据每次都分成两份然后再去找到你想要的数据,我们可以这样去想,二分法查找很类似与我们平时玩的猜价格游戏,当你报出一个价格时裁判会告诉你价格相对于真实值的高低,倘若是低了那我们一定会再说出一个略高的价格,反之亦然。在二分法查找时要求传入的数据必须已经有序,假设现在为升序,然后每次将所寻找的值与中间值(数组左边界+(右边界-左边界)/2)作比较,大了则去寻找中间值左侧数据,小则寻找中间值右侧数据。
二分法查找比较局限性的就是只能操作一个已经排序了的数组。
方法一
下面为一个二分法实现的完整代码
package dichotomy;
import java.util.Arrays;
import java.util.Scanner;
import static java.lang.System.out;
public class Erchange {
private static Scanner in;
public int find(int a[],int b) //a为所要查找的数
{
int mid,low=0,high;
high=a.length-1;
while(low<=high)
{
mid=low+(high-low)/2;
if(b<a[mid])
{
high=mid-1;
}
else if(b>a[mid])
{
low=mid+1;
}
else
{
return mid+1;
}
}
return 0;
}
public static void main(String[] args) {
int a[];
int t;
int sum=0;
Erchange p=new Erchange();
int q2 = 0;
in = new Scanner(System.in);
out.println("请输入数组长度");
q2= in.nextInt();
a=new int [q2];
out.println("请输入数组元素");
for(int i=0;i<a.length;i++)
{
a[i]=in.nextInt();
}
out.println("排序后数组为");
Arrays.sort(a);
for (int i = 0; i < a.length; i++) {
out.print(a[i]+" ");
}
out.println();
out.println("请输入所要查找的数若未查找到该数则输出-1");
q2=in.nextInt();
for(int i=0;i<a.length;i++)
{
if(q2==a[i])
{
t=1;
}
else
{
t=0;
}
sum=sum+t;
}
if(sum==0)
{
out.println("-1");
}
else
{
out.println("所输入的数在第"+p.find(a,q2)+"位");
}
}
方法二
代码实现:
public class BinarySearch {
//进行二分法查找的前提是数组已经有序!
public static int rank(int key,int nums[])
{
//查找范围的上下界
int low=0;
int high=nums.length-1;
//未查找到的返回值
int notFind=-1;
while(low<=high)
{
//二分中点=数组左边界+(右边界-左边界)/2
//整数类型默认取下整
int mid=low+(high-low)/2;
//中间值是如果大于key
if(nums[mid]>key)
{
//证明key在[low,mid-1]这个区间
//因为num[mid]已经判断过了所以下界要减一
high=mid-1;
}else if(nums[mid]<key)
{
//证明key在[mid+1,high]这个区间
//同样判断过mid对应的值要从mid+1往后判断
low=mid+1;
}
else
{
//查找成功
return mid;
}
}
//未成功
return notFind;
}
public static void main(String[] args) {
System.out.println("请输入数据数量:");
Scanner scanner=new Scanner(System.in);
int amount=scanner.nextInt();
int num;
int nums[]=new int[amount];
int i=0;
while(i<amount)
{
nums[i]=scanner.nextInt();
i++;
}
Arrays.sort(nums);
System.out.println("请输入想要查找的值");
int key=scanner.nextInt();
int answer=rank(key,nums);
if(answer!=-1)
{
System.out.println("所查找的数据存在:"+nums[answer]);
}
else
{
System.out.println("您所查找的数据不存在");
}
}
}
方法三、算法代码实现之二分法查找
封装成类:
package com.roc.algorithms.search;
/**
* 二分法查找
*
* @author roc
*/
public class BinarySearch {
/**
* @param a 升序排列的数组
* @param k 待查找的整数
* @return 如果查到有就返回对应角标,没有就返回-1
*/
public static int search(int[] a, int k) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int m = (lo + hi) >> 1;
if (a[m] < k) {
lo = m + 1;
} else if (a[m] > k) {
hi = m - 1;
} else {
return m;
}
}
return -1;
}
}
测试:
int[] a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(BinarySearch.search(a, 6));
输出:
6
来源:https://blog.csdn.net/qq_40833779/article/details/80095715
0
投稿
猜你喜欢
- 这篇文章主要介绍了基于spring security实现登录注销功能过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的
- 本文实例为大家分享了AJAX二级联动效果的具体代码,供大家参考,具体内容如下Ajax.jsvar createAjax = function
- 对于使用文件进行交换数据的应用来说,使用FTP 服务器是一个很不错的解决方案。关于FileZilla Server服务器的详细搭建配置过程,
- MyBatis的前身叫iBatis,本是apache的一个开源项目, 2010年这个项目由apache software foundatio
- 详解java 中Spring jsonp 跨域请求的实例jsonp介绍  
- 适配器(Adapter)模式:适配器模式把一个类的接口变换成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够在一
- java模拟TCP通信实现客户端上传文件到服务器端,供大家参考,具体内容如下客户端package com.zr;import java.io
- 一、什么是抽象工厂模式为创建一组相关或相互依赖的对象提供一个接口,而且无需指定他们的具体类。抽象工厂模式是所有形态的工厂模式中最为抽象和最具
- 具体可见http://developer.android.com/tools/debugging/ddms.html。 DDMS为IDE和e
- 一、链表的介绍什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结
- yield()介绍yield()的作用是让步。它能让当前线程由“运行状态”进入到“就绪状态”,从而让其它具有相同优先级的等待线程获取执行权;
- 茫茫人海千千万万,感谢这一秒你看到这里。希望我的面试题系列能对你的有所帮助!共勉!愿你在未来的日子,保持热爱,奔赴山海!Java基础知识(继
- 字节流和字符流对于文件必然有读和写的操作,读和写就对应了输入和输出流,流又分成字节和字符流。1.从对文件的操作来讲,有读和写的操作——也就是
- 0x01 新建SpringBoot项目1. 新建maven工程ps:在上一教程的基础上操作,就不用新建项目了,请参考文章:SpringBoo
- 这篇文章主要介绍了SpringBoot FreeWorker模板技术解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考
- 使用过 mybatis 框架的小伙伴们都知道,mybatis 是个半 orm 框架,通过写 mapper 接口就能自动实现数据库的增删改查,
- 本文实例讲述了Java操作Mongodb数据库实现数据的增删查改功能。分享给大家供大家参考,具体如下:首先,我们在windows下安装mon
- 一、准备官网下载IntelliJ IDEA 2017 并安装好下载汉化包 (链接: https://pan.baidu.com/s/1JkU
- 本文实例为大家分享了C语言自定义扫雷游戏的具体代码,供大家参考,具体内容如下实现过程对于用C语言实现扫雷游戏得实现,可将游戏过程分为两个板块
- 本文为大家分享了使用静态关键字实现单例模式的具体代码,供大家参考,具体内容如下单例模式:只能获得某个类的唯一一个实例单例模式,不管什么时间点