文档章节

Java面试必备知识点梳理:二分查找算法

博文视点Bv
 博文视点Bv
发布于 11/20 09:37
字数 1648
阅读 23
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

file

在计算机世界里“数据结构+算法=程序”,因此算法在程序开发中起着至关重要的作用。虽然我们在开发中自己设计算法的情况不多,在工作中却离不开算法。无论是开发包提供的算法还是我们自己设计的算法,算法在程序中都无处不在。

file

常用的算法有查找算法和排序算法。查找算法有线性查找算法、深度优先搜索算法、广度优先搜索算法和二分查找算法,而最常用也最快速的就是二分查找算法了。

二分查找算法又叫作折半查找,要求待查找的序列有序,每次查找都取中间位置的值与待查关键字进行比较,如果中间位置的值比待查关键字大,则在序列的左半部分继续执行该查找过程,如果中间位置的值比待查关键字小,则在序列的右半部分继续执行该查找过程,直到查找到关键字为止,否则在序列中没有待查关键字。

file

下图中,在有序数组[3,4,6,20,40,45,51,62,70,99,110] 中查找key=20的数据,根据二分查找算法,只需查找两次便能命中数据。

file

这里需要强调的是,二分查找算法要求要查找的集合是有序的,如果不是有序的集合,则先要通过排序算法排序后再进行查找。

二分查找算法的Java实现如下,代码定义了方法binarySearch()用于二分查找,在该方法中有3个变量low、mid和high,分别表示二分查找的最小、中间和最大的数据索引。

 1     publicstatic int  binarySearch(int []array,inta){
 2        intlow=0;
 3        inthigh=array.length-1;
 4        intmid;
 5       while(low<=high){
 6           mid=(low+high)/2;//中间位置
 7           if(array[mid]==a){
 8               return mid;
 9           }else if(a>array[mid]){ //向右查找
10               low=mid+1;
11           }else{ //向左查找
12               high=mid-1;
13            }
14        }
15       return -1;
16    }

在以上代码中,通过一个while循环在数组中查找传入的数据,在该数据大于中间位置的数据时向右查找,即最大索引位置不变,将最小索引设置为上次循环的中间索引加1;在该数据小于中间位置的数据时向左查找,即最小索引位置不变,然后将最大索引设置为上次循环的中间索引并减1。重复以上过程,直到中间索引位置的数据等于要查找的数据,说明找到了要查找的数据,将该数据对应的索引返回。如果遍历到low>high还没有找到要查找的数据,则说明该数据在列表中不存在,返回-1。

file

面试官通常会在短短两小时内对面试者的知识结构进行全面了解,面试者在回答问题时如果拖泥带水且不能直击问题的本质,则很难充分表现自己,最终影响面试结果。

针对这种情况,**《Offer来了:Java面试核心知识点精讲(原理篇)》**一书出版上市。本书在讲解知识点时不拖泥带水,力求精简,详细介绍了Java程序员面试时常被问及的核心知识点。 file

面试在即,Java知识点很凌乱?别急,本书是对Java程序员面试必备知识点的总结,详细讲解了JVM原理、多线程、数据结构和算法、分布式缓存、设计模式等内容,除了原理讲解,还有Java实现!希望本书能够帮助你对Java的基础原理有更深入、全面的理解。

面试时的原理+动手实现脑海已就位,整装待发!互联网寒冬怕什么~

▉ 关于作者

王磊,现任国内某知名互联网公司大数据技术架构师,有十余年丰富的物联网及大数据研发和技术架构经验,对物联网及大数据的原理和技术实现有深刻的理解。长期从事海外项目的研发和交付工作,对异地多活数据中心的建设及高可用、高并发系统的设计有丰富的实战经验。

▉ 大咖推荐

  • 杨彪 / 美团高级架构师,《可伸缩服务架构》《分布式服务架构》作者
  • 知秋(simviso) / Java编程方法论系列书籍作者
  • 王新栋 / 京东资深架构师,《架构修炼之道》作者

▉ 章节架构

第1章 讲解JVM原理,涉及JVM运行机制、JVM内存模型、常用垃圾回收算法和JVM类加载机制等内容。

第2章 讲解Java基础知识,涉及集合、异常分类及处理、反射、注解、内部类、泛型和序列化等内容。

第3章 讲解Java并发编程知识,涉及Java多线程的工作原理及应用、Java线程池的工作原理及应用,以及锁、进程调度算法等内容。

第4章 讲解数据结构知识,涉及栈、队列、链表、散列表、二叉树、红黑树、图和位图等内容。

第5章 讲解Java中的常用算法,涉及二分查找、冒泡排序、插入排序、快速排序、希尔排序、归并排序、桶排序、基数排序等算法。

第6章 讲解网络与负载均衡原理,涉及TCP/IP、HTTP、常用负载均衡算法和LVS原理等内容。

第7章 讲解数据库及分布式事务原理,涉及数据库存储引擎、数据库并发操作和锁、数据库分布式事务等内容。

第8章 讲解分布式缓存的原理及应用,涉及分布式缓存介绍、Ehcache原理及应用、Redis原理及应用、分布式缓存设计的核心问题等内容。

第9章 讲解设计模式,涉及常见的23种经典设计模式。

了解本书详情

本文由博客一文多发平台 OpenWrite 发布!

© 著作权归作者所有

博文视点Bv
粉丝 0
博文 18
码字总数 44574
作品 0
私信 提问
如何理解并掌握 Java 数据结构

一说起“数据结构”可能很多同学都又交给老师了。但是实际工作中如果做得深入一些,特别是越往上发展,越大公司越离不开数据结构。本场 Chat 作者将带领大家重温《Java 数据结构》,讲解的内...

valada
2018/04/12
0
0
二分查找 : 那个隐藏了 10 年的 Java Bug

原文出处:ccmouse 一个偶然的机会,我想起以前还在谷歌上班的时候,有时候大家会在饭桌上讨论最新想出来的一些面试题。在众多有趣又有难度的题目中,有一道老题却是大家都纷纷选择避开的,那...

ccmouse
2017/09/02
0
0
算法知识梳理(8) - 二分查找算法及其变型

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/12
0
0
内存优化(使用SparseArray和ArrayMap代替HashMap)

支持原文:http://tryenough.com/java-sparseArray HashMap 关于HashMap的知识请看这篇 优秀文章: SparseArray SparseArray 的使用 支持原文:http://tryenough.com/java-sparseArray 创建 ......

TryEnough
03/12
0
0
动画:二分查找(下) |面试官问我如何在 20 万 IP 地址中快速定位某一归属地?

写在前边 上回讲到,如何在 1 亿数据中查找一个整数,重新认识了二分查找,二分查找的适用条件以及手写代码时应该注意到的细节问题。 动画:面试官问我如何在 1 亿数据中快速查找某一整数?(...

小鹿动画学编程
11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

阿里巴巴的 Kubernetes 应用管理实践经验与教训

作者 | 孙健波(天元) 阿里巴巴技术专家 导读:本文整理自孙健波在 ArchSummit 大会 2019 北京站演讲稿记录。首先介绍了阿里巴巴基于 Kubernetes 项目进行大规模应用实践过程中遇到的问题;...

阿里巴巴云原生
19分钟前
3
0
pinpoint采样原理分析

使用pinpoint进行全链路监控时,支持对请求的采样,某条请求是否被采样,取决于整个链路开始的机器。该机器使用特定的采样算法。采样的标志会一直在链路中透传。比如在http里面,会在header里...

xiaomin0322
24分钟前
3
0
在IDEA开发工具中使用lombok

1. 首先我们需要安装IntelliJ IDEA中的lombok插件,打开IntelliJ IDEA后点击菜单栏中的File-->Settings,或者使用快捷键Ctrl+Alt+S进入到设置页面 我们点击设置中的Plugins进行插件的安装,在...

欧阳飘
25分钟前
3
0
爱码仕 5G生活畅想 (五) 每个人每个家庭都有一朵私有的云

30年前,微软让每个家庭都有一台电脑的理念成为了现实;而今云计算的观念已为老百姓们所熟识。数据就是能源;数据就是财富;谁生产了数据,这数据的所有权就归谁所有。随着原生云基础设施的完...

LitStone
27分钟前
3
0
嵌入式入门:嵌入式领域的职业发展方向是什么?

嵌入式入门:嵌入式领域的职业发展方向是什么? 在如今的IT市场上看,嵌入式的发展的应用都是广受欢迎的,在嵌入式入门学习中,我们可以发现嵌入式的发展方向有很多,门槛高低不一样。下面就...

xyd118
27分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部