Java实现二分查找算法实例分析
作者:tolcf 发布时间:2022-06-01 07:30:32
标签:Java,二分查找,算法
本文实例讲述了Java实现二分查找算法。分享给大家供大家参考。具体如下:
1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序
2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。可能描述得不是很清楚,若是不理解可以去网上找。从描述上就可以看出这个算法适合用递归来实现,可以用递归的都可以用循环来实现。所以我们的实现分为递归和循环两种,可以根据代码来理解算法
实现代码:
public class BinarySearch {
public static void main(String[] args){
int searchArr[] = new int[1000000];
for(int i=0;i<1000000;i++){
searchArr[i]=i;
}
System.out.println(binSearch(searchArr,0,searchArr.length-1,99));
System.out.println(binSearch(searchArr,99));
}
//递归二分查找
public static int binSearch(int arr[], int start,int end,int sear){
int mid = (end-start)/2 + start;
if(sear==arr[mid]){
return mid;
}
if(start>=end){
return -1;
}else if(sear < arr[mid]){
return binSearch(arr,0,mid-1,sear);
}else if(sear >arr[mid]){
return binSearch(arr,mid+1,end,sear);
}
return -1;
}
//循环二分查找
public static int binSearch(int arr[],int key){
int mid = arr.length/2;
int start = 0;
int end = arr.length-1;
while(start<=end){
mid = (end-start)/2+start;
if(key ==arr[mid]){
return mid;
}else if(key <= arr[mid]){
end = mid-1;
}else if(key >=arr[mid]){
start = mid+1;
}
}
return -1;
}
效率比较:
循环二分查找算法的效率高于递归二分查找算法
希望本文所述对大家的java程序设计有所帮助。
0
投稿
猜你喜欢
- 质数又称素数。一个大于1的自然数,如果除了1和它自身外,不能被其他自然数整除的数;否则称为合数。根据算术基本定理,每一个比1大的整数,要么本
- Tomcat 如何实现WebSocketWebSocket协议属于HTML5标准,越来越多浏览器已经原生支持WebSocket,它能让客户端
- 文章来源:csdn 作者:chensheng913对于Java语言,最体贴的一项设计就是它并没有打算让人们为了写程序而写程序——人们也需要考
- 面试题1:谈一下你对 Nginx 的理解Nginx 是一款自由的、开源的、高性能的 HTTP 服务器和反向代理服务器;同时也是一个 IMAP
- synchronized原理在java中,每一个对象有且仅有一个同步锁。这也意味着,同步锁是依赖于对象而存在。当我们调用某对象的synchr
- 我已经很精简了,两篇(Spring Boot启动过程(一)、spring Boot启动过程(二))依然没写完,接着来。refreshCont
- 一、说明Boost.MPI 提供了 MPI 标准(消息传递接口)的接口。该标准简化了并发执行任务的程序的开发。您可以使用线程或通过共享内存或
- 1、首先创建一个测试实体类Person,并携带如上注解,其注解的作用描述在messagepackage com.clickpaas.pojo
- BeanUtils.copyProperties无法封装使用BeanUtils.copyProperties(user, memeber);
- 源程序揭秘杨辉三角形性质: 每行数字左右对称,由 1 开始逐渐变大,然后变小,回到 1。 第 n 行的数字个数为 n 个。 第 n 行数字和
- 本文实例讲述了Java实现文件和base64流的相互转换功能。分享给大家供大家参考,具体如下:import java.io.FileInpu
- 上一章节回顾:Netty分布式源码分析监听读事件概述pipeline, 顾名思义, 就是管道的意思, 在net
- 本文研究的主要是优化MyBatis配置文件中的配置的相关内容,具体介绍如下。一、连接数据库的配置单独放在一个properties文件中之前,
- Navigator 的 push 和 pop方法Navigator 导航器的 push 和 pop 方法可以携带参数在页面间传递,其他变形的
- 前言windows自带的游戏《扫雷》是陪伴了无数人的经典游戏,本程序参考《扫雷》的规则进行了简化,用java语言实现,采用了swing技术进
- 官网教程一、翻转(镜像)头文件 quick_opencv.h:声明类与公共函数#pragma once#include <opencv
- Feign的作用是将Http请求抽象化为一个Interface客户端,可以调用接口的形式来执行Http请求,以达到简化Http调用的目的。F
- 1. 前言Spring最重要的一个概念当属Bean了,我们写的Controller、Service、Dao凡是加了对应注解交给Spring管
- 背景在接口请求过程中,传递json对象,springboot转换为实体VO对象后,所有属性都为null。post请求:后台接收请求:当时就懵
- 实例如下:import java.lang.reflect.Field;import java.lang.reflect.Invocatio