面试官,我会写二分查找法!对,没有 bug 的那种!

五分钟学算法 2019-06-12 11:24:00 阅读数:32 评论数:0 收藏数:0

前言科普

第一篇二分搜索论文是 1946 年发表,然而第一个没有 bug 的二分查找法却是在 1962 年才出现,中间用了 16 年的时间。

2019 年的你,在面试的过程中能手写出没有 bug 的二分查找法么?

定义

在计算机科学中,二分查找(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法

搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;

如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空,则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找法代码

按照上面的定义,我们来尝试写一下二分查找法的代码。

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            mid = (min + max) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

现在问你,上面的代码有没有问题?哪段代码会出现 bug ?

请思考一分钟后再往下查看。

对于上面这段代码而言,问题出在第 6 行代码处:

mid = (min + max) / 2;

这句代码在 min 和 max 很大的时候,会出现溢出的情况,从而导致数组访问出错。

别看现在轻描淡写的指出了这个错误,但这个错误在当时可是存在了好些年。

那怎么改进呢?一般的做法是这样的:将加法变成减法。

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 防止溢出
            mid =  min + (max - min) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

还有一种更高逼格的写法,也是官方的二分搜索法的实现写法:使用 位运算

 public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 无符号位运算符的优先级较低,先括起来
            mid =  min + ((max - min) >>> 1);
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

希望通过今天的文章能帮助读者们在面试中手写对代码,毕竟,对于很多小公司来说,二分查找法会出现在他们的笔试题中的。

 


版权声明:本文为[五分钟学算法]原创文章
转载请带上:http://copyfuture.com/blogs-details/201906121125016643tkey4iwqyvj0ma
或:https://www.cnblogs.com/fivestudy/p/11008521.html



  1. 再也回不到原厂巅峰状态为什么说本田发动机一拆就废?
  2. MIT新技术:你的窃窃私语能让数米外某个耳朵听到
  3. Vue组件化开发
  4. js事件循环机制 (Event Loop)
  5. 印象笔记升级后,我更爱苹果电脑了!
  6. 『伤感短句』你是我终生不治之顽疾疫病,始于心动终结于枯骨飞灰
  7. Python 面向对象进阶
  8. 孟美岐晒火箭少女101美国聚餐:peace & love
  9. 杜兰特再给出下家暗示,原来他早已表忠心
  10. 2018年终总结(二)得和失
  11. AI公开课:19.03.27韦韬—百度CSS《AI产业面临的安全威胁与挑战》课堂笔记以及个人感悟
  12. RealSense R400系列深度相机的彩色和深度图像获取
  13. NHibernate之旅(10):探索父子(一对多)关联查询
  14. SpringCloud Ribbon 负载均衡 通过服务器名无法连接的神坑一个
  15. 有趣的 box-decoration-break
  16. shp系列(三)——利用C++进行DBF文件的读(打开)
  17. Lady Gaga或将参演《赛博朋克2077》
  18. “东北王”张作霖的八个儿子们,结局怎么样了?
  19. 《步步》若兰羡慕明慧能嫁喜欢的人,明慧却羡慕她能得到丈夫的心
  20. 日本最牛的摩托车,比一辆豪华宝马轿车还要贵,限量100台!
  21. Web API 处理机制剖析 --- 拨开迷雾看本质
  22. 2044年美国白人将变少数族裔?近半数白人表担忧
  23. 小米9开源内核代码,上市即开源
  24. 即将起降歼15!中国002航母开始第5次海试,专家:半年内服役
  25. BugkuCTF~代码审计~WriteUp
  26. 吉利版 “X6” 实车到店啦!价格曝光 蛮亲民的!
  27. AMD发布Ryzen 7 3700X/3800X:力压Intel 9700K/9900K
  28. SQL Server数据库漏洞评估了解一下
  29. 好心情能预防糖尿病?降血糖,学会化解不良情绪很重要!
  30. 微波炉中两颗葡萄会变火球?科学家炸了12台微波炉终解多年谜题!
  31. ES6躬行记(19)——生成器
  32. 朝鲜的前世今生:“善变”的朝鲜
  33. 我们的生活可能好,可能糟糕,但最棒的是我们总还有选择的余地
  34. 除了期待已久的黑暗模式,我们还能从 iOS 13 的更新中看到什么
  35. 望京SOHO风水克死一堆公司,连王思聪都没躲过?
  36. 净月潭名称的由来
  37. 德系、日系、法系车都适合什么机油,记住一个标号就行.
  38. LG将自主研发人工智能芯片 为其手机提供支持
  39. 第9章 用户自己建立数据类型
  40. 为产品接入微信支付解决方案(公司&个人)
  41. 中国海军远洋舰队巨舰的起点,我们不能忘记此船是原型
  42. [算法xio讲堂#2]线段树
  43. 在黑河冰雪的洗礼下测评锐界 这次我们是认真的(上)
  44. 一线|任正非:5G技术别人两三年肯定追不上华为
  45. 持续集成之应用k8s自动部署
  46. Windows系统下安装Redis
  47. 来自一个弱校OIer的NOIP2018冲刺计划
  48. NASA火星直升机完成飞行测试
  49. 如何判断是否被网关或ISP劫持了DNS或HTTP流量?
  50. 新东方在线联席CEO孙畅&孙东旭联名内部信:上市不是终极目标
  51. Spark2.1.0——深入理解事件总线
  52. 三篇文章带你极速入门php(二)之迅速搭建php环境
  53. 最牛的创业者,每天都在轻度喜悦和轻度沮丧之间
  54. 沉浸式图片轮播器 -- DDGBannerScrollView使用文档
  55. 从壹开始[做贡献]之二 || 推荐VSCode多语言开发,支持一键JAVA
  56. linux命令(1)
  57. 一口气八集,这青春剧甜到预告都不放过
  58. 所向无敌的马其顿方阵是如何走下神坛的?
  59. 中国非法劳工在菲引热议!菲参议员:赶也不是,不赶也不是
  60. 科创板1号华兴源创被质疑涉嫌严重欺骗 券商聘请会计师审核财务
  61. 苹果或3月25开发布会,新iPad型号为A2124和A2133,10.2寸受欢迎
  62. 明清奇案之谁动了我的银子
  63. 链表(一)
  64. 宝可梦GO开发商再造一款AR新作 硬核HP粉丝向
  65. 这个机器人已经有181岁 名叫安卓 难道是穿越了
  66. 韩国检方就三星生物财务造假案搜查其办公室
  67. 观点铿锵行:股市与楼市
  68. Linux 工程向 Windows 平台迁移的一些小小 tips
  69. HTTP协议及其相关
  70. 大批90后步入中年, 催促他们成长的究竟是岁月还是现实?
  71. 谁还敢坐?波音飞机去年至今葬送458条人命 空难频频谁的错?
  72. Fuzzy finder(fzf+vim) 使用入门指南
  73. 学生轻生之反思:呼唤生命教育,安全教育不可缺失
  74. 浅谈MVVM模式和MVP模式——Vue.js向
  75. SpringBoot使用JNDI数据源
  76. ASP.NET MVC雕虫小技 1-2
  77. JavaScript基础部分经典案例
  78. 尿酸高引起痛风,高尿酸是否需要服药呢?来看看医生怎么说
  79. 电子烟中小企业惧资本过度介入:不想行业成为下一个共享单车
  80. 为什么明朝军事那么牛逼,却被清朝给消灭了呢?
  81. 《逆袭大学——传给IT学子正能量》CSDN连载目录
  82. 远程调试与监控 --jmx & remote debug
  83. 比尔·盖茨:用意想不到的方法诊断阿尔茨海默症
  84. 网络编程详解-含一些开发总结
  85. 关于演讲认知和技巧的一些分享
  86. 除了平坝“网红”樱花园,贵州还有一大波小众绝美的赏花地!人少景美,速去!
  87. “香椿自由”的同时也要小心风险
  88. 比亚迪抓紧吧,这家美国电动卡车可真“擎天柱”
  89. 导致餐后血糖升高的6个坏习惯,看看你有吗
  90. 微软宣布新 Kinect for Windows外设:Azure Kinect DK
  91. 小姐姐不仅给奥迪A3改装换新颜,还是最强王者
  92. 六旬老人外出旅游时,无意中拍到乐山大佛的秘密,还获赔280万
  93. 梵蒂冈、医院骑士团、圣马力诺三个袖珍国家为何都在意大利境内
  94. 上饶10岁男生被同学家长刺死 当天班主任本约双方面谈
  95. Tiobe指数5月份编程语言排行榜详情
  96. 魏建军一招制敌,巴博斯版WEY将推出,网友:领克要被甩几条街
  97. 逆袭的印度:高超音速武器默默开花结果、战略威慑力被全世界低估
  98. 宝宝出现这个动作,说明他根本就没吃饱……
  99. 从零开始开发一个vue组件打包并发布到npm (把vue组件打包成一个可以直接引用的js文件)
  100. asp.net core 系列 4 注入服务的生存期

  1. 前端笔记之NodeJS(一)初识NodeJS&内置模块&特点(1755)
  2. Matlab 2019a 安装包下载以及安装和激活(1719)
  3. Delphi 开发微信公众平台 (二) 用户管理(1679)
  4. Python开发:部分第三方库无法在线安装解决方法(1563)
  5. React 与 React-Native 使用同一个 meteor 后台(1429)
  6. 《跃迁-成为高手的技术》之联机学习(1427)
  7. [深度应用]·实战掌握Dlib人脸识别开发教程(1427)
  8. 独家 | 寒武纪二代芯片发布在即,提前解密如何挑战英伟达!(1370)
  9. 使用 C 语言实现一个 HTTP GET 连接(1352)
  10. 币安称 4000 万美元比特币被盗(1316)
  11. WebGL three.js学习笔记 纹理贴图模拟太阳系运转(1237)
  12. 微软宣布 .NET 5 计划,支持跨平台、移动开发(1189)
  13. C#读取excel文件提示未在本地计算机上注册“Microsoft.ACE.OLEDB.12.0”提供程序(1186)
  14. 【译】.NET Core 是 .NET 的未来(1162)
  15. Linux学习(三):XShell连接虚拟机+开通22端口(1135)
  16. layui的table参数条件缓存问题(1114)
  17. 75条笑死人的知乎神回复,用60行代码就爬完了(1103)
  18. 2019年程序员最值得学习的思维利器——任务分解(971)
  19. 10亿元巨贪山西吕梁原副市长张中生二审维持死刑判决(958)
  20. Sublime Text3 最新版3207 安装及破解(947)
  21. 声明与定义的区别(889)
  22. 美方拟升级关税措施?中方:反制!(880)
  23. 绿盟科技互联网安全威胁周报NSFOCUS-19-13(870)
  24. css-博客样式初体验(843)
  25. 小米有品员工签军令状,自动放弃年终奖!(827)
  26. Vue之路由(815)
  27. 科学家在太平洋水域发现奇特的“砷呼吸”微生物(804)
  28. 【预警通告】Weblogic反序列化远程代码执行漏洞(779)
  29. Visual Studio 2019 正式发布,重磅更新,支持live share(742)
  30. 【预警通告】Apache Tomcat远程代码执行漏洞CVE-2019-0232(725)
  31. 【威胁通告】Oracle全系产品2019年4月关键补丁更新(703)
  32. SQL简介及MySQL的安装目录详解(683)
  33. 5月13日公告精读丨一字跌停后,这只300亿市值的白马股出来澄清了(653)
  34. 如果想转行学习WEB前端,这样学也许更加利于找工作(651)
  35. 彭博社:苹果A13芯片即将产量 新iPhone"浴霸"无疑(591)
  36. K8s集群安装--最新版 Kubernetes 1.14.1(567)
  37. MongoDB创建数据库和删除数据库05-14学习笔记(541)
  38. Confluence SSRF及远程代码执行漏洞处置手册(534)
  39. 吴奇隆当爹!前妻马雅舒开心复出拍戏,颜值吸睛气质超赞(532)
  40. PJzhang:Lucifer1993的struts-scan漏洞全量检测工具(531)
  41. 英媒:阿里将允许外国零售商在阿里平台上销售商品(529)
  42. 舍命生子产妇吴梦丈夫怒斥:没抢肺源不是精神分裂,网友断章取义(521)
  43. Visual Studio 2019 正式发布(511)
  44. [翻译] Visual Studio 2019: 极速编码. 智能工作. 创造未来.(485)
  45. 机器学习 ML.NET 发布 1.0 RC(478)
  46. 【硬盘版】下载利器IDM+优特(uTorrent)BT下载器类(473)
  47. 刘强东身边的CXO还有谁“幸存”(469)
  48. 阿里巴巴2018年纳税516亿元 同比增40%(468)
  49. 针对django2.2报错:UnicodeDecodeError: 'gbk' codec can't decode byte 0xa6 in position 9737: ill....(465)
  50. 马光远:全球货币政策进入摇摆期,包括房价的资产价格何去何从(434)
  51. 太奇葩!买100元债只给1.63元购物券和1.11元现金?网友炸锅:得买多少债券才能换一双鞋(421)
  52. 雷军清华演讲实录:小米9年的创新、变革与未来(420)
  53. 我司使用了六年的分布式锁(419)
  54. Webpack 4教程 - 第八部分 使用prefetch和preload进行动态加载(405)
  55. 他联系叙恐怖分子“卖军火”,称能搞到2000枚导弹,关键时刻中国警察出手(404)
  56. Spring Boot 2.1.5 正式发布,1.5.x 即将结束使命!(402)
  57. F#周报2019年第14期(402)
  58. 《最强大脑》要垮?桑洁魏坤琳出轨细节被扒,戚薇才是神助攻(389)
  59. 直认与老公感情淡了!27岁TVB上位女星:我们不是好熟(382)
  60. 报告显示:一季度中国家庭总资产缩水而消费支出增加(375)
  61. 那些年,我们一起看的毛片(373)
  62. 谁是苏小明饭局爆粗偷拍者?知情人称另有其人(360)
  63. 苹果应用商店被判垄断?然而并没有(357)
  64. linux系统安装cdcfordb2udb(351)
  65. 如何设置使chrome新标签页中打开链接自动跳转到新标签页?(350)
  66. 迪玛希好惨!昨晚《歌手》为声入人心男团帮帮唱,却再被指控侵权(349)
  67. 女友被曝插足许志安郑秀文婚姻 知情人透露马国明已下定决心分手(346)
  68. 华电教授孙玉兵被指与昔日同学共同学术造假,多所高校调查(345)
  69. 智慧停车场系统开发建设解决方案(343)
  70. F#周报2019年第15期(332)
  71. spring-cloud-sleuth+zipkin源码探究(332)
  72. 深度学习python的配置(Windows)(325)
  73. 许志安出轨视频系蓄谋偷拍?司机被曝收40万装红外摄像头(323)
  74. 威廉王子出轨凯特王妃闺蜜? 外媒称婚外情致兄弟反目(323)
  75. 真实!这部8.5分的缉毒剧,毒贩公然贿赂警察:80万,把我放出去(316)
  76. NodeJs之邮件(email)发送(316)
  77. 视觉中国深夜道歉:全面配合监管部门彻底积极整改(313)
  78. 赌命生子九个月后,吴梦离世:前半辈子任性了,我用生命买单(311)
  79. 新更新kb4493472导致无法正常开机(306)
  80. 她做个半永久眉毛就被说整容了?(301)
  81. 第一次使用VS Code时你应该知道的一切配置(299)
  82. 韦杰落网,金诚集团终局(298)
  83. 山东庆云民企3000亩土地被贱卖 国企接盘拟转性(298)
  84. 华为推出方舟编译器 称可提升安卓系统效率(295)
  85. Google AI 系统 DeepMind 高中数学考试不及格(294)
  86. 读书笔记之《漫画算法:小灰的算法之旅》(293)
  87. 不要996!程序员创建955.WLB不加班公司名单,GitHub周榜第二(292)
  88. 机器学习基石笔记:01 The Learning Problem(291)
  89. 张丹峰出轨最新锤来了!毕滢的朋友圈简直刷新下限啊!(290)
  90. React Native升级方法——升级到最新版本0.59(287)
  91. axios(封装使用、拦截特定请求、判断所有请求加载完毕)(286)
  92. “国防”靠美国? 韩国瑜=马英九2.0? 走着瞧(280)
  93. 吹爆惠英红,《铁探》这位霸道总警司超带感!真乃港剧罕见大女主(279)
  94. Leetcode刷题指南和top100题目(275)
  95. 河南汝州农商行“百万丢款案”调查,两级法院现“判决书打架”(270)
  96. 堪称神器的Chrome插件(266)
  97. Codejam Qualification Round 2019(264)
  98. Weblogic CVE-2019-2647等相关XXE漏洞分析(263)
  99. CentOS7 部署zabbix4.2及添加客户端(261)
  100. 中国海军的逆袭之路(255)

  1. 【威胁通告】WebSphere远程代码执行漏洞(CVE-2019-4279)
  2. 市场平静蓄势,变盘窗口临近?(6月26日)
  3. Hadoop 三剑客之 —— 集群资源管理器 YARN
  4. 他在混沌中寻找秩序
  5. ES6新特性
  6. windows10安装nodejs 10和express 4
  7. 爱立信携手联发科技,联合中国电信完成5G SA端到端数据呼叫
  8. 周鸿祎谈华为鸿蒙系统:可以打造成安卓一样的开源系统
  9. Java基础--常用API--IO流相关API
  10. Spring AOP APIS
  11. 周杰伦为儿子庆生一家合照曝光,炫妻晒娃两不误
  12. Adobe cs6 全系列软件绿色破解版-一键安装
  13. Kafka主题中的分区数越多吞吐量就越高?BULLSHIT!!!
  14. 数据结构与算法(一):带你了解时间复杂度和空间复杂度到底是什么?
  15. Spring Schema扩展机制
  16. 线程安全
  17. 14.Python略有小成(模块)
  18. 为了追求极致的性能,Kafka掌控这11项要领
  19. 特斯拉负责汽车制造的副总裁在关键时期离职
  20. .NET程序员如何快入门Spring Boot
  21. Laravel5.x的php artisan migrate数据库迁移创建操作报错SQLSTATE[42000]解决
  22. hibernate和mybatis的区别?
  23. Qemu搭建ARM vexpress开发环境(二)----通过u-boot启动Linux内核
  24. 295亿宁波首富宣告破产!登顶首富到破产仅247天,千亿房企又倒一个?
  25. DIgital Root 的推导
  26. nRF24L01+组网方式及防撞(防冲突)机制的实战分享
  27. LinqMethod 实现 LeftJoin
  28. 苹果若将生产线转移到中国之外,到底有多难?
  29. 通过OSG实现对模型的日照模拟
  30. maven项目或者SpringBoot项目启动时报错在本地仓库中找不到jar包的解决办法
  31. 伊朗击落美军的无人机为啥一打一个准?俄罗斯有话要说
  32. 《柳叶刀》重磅报告,这是当今中国最严重的4大死亡风险因素
  33. python之mock模块基本使用
  34. 递归(三):排列
  35. 【搜索引擎】Solr Suggester 实现全文检索功能-分词和和自动提示
  36. 山口百惠 VS. 中岛美雪,成功女性的人生哪有什么固定模式
  37. 联想发布全球首款5G笔记本电脑 搭载8CX平台+X55模块
  38. 创业板龙头易主!迈瑞医疗最新市值1923亿元,赶超温氏股份
  39. 中国科技公司拥抱国产数据库
  40. 【数据结构】30、hashmap=》hash 计算方式
  41. ES6——class类继承(读书笔记)
  42. .NET Core 微服务之Polly熔断策略
  43. JavaScript系列之JS入门基本语法
  44. 7xex交易所——服务于全球交易用户的创新数字资产交易平台
  45. Python魔法方法__getattr__和__getattribute__详解
  46. 为了招BAT的程序员,年前把老员工辞掉,一个月后公司后悔了
  47. AspNetCore容器化(Docker)部署(四) —— Jenkins自动化部署
  48. python requests模块session的使用建议及整个会话中的所有cookie的方法
  49. 聊聊区块链,虽然我不挖矿!
  50. Laravel:php artisan key:generate三种报错解决方案,修改默认PHP版本(宝塔面板)
  51. (11)《数据结构与算法》之赫夫曼树
  52. 首次!腾讯全面公开整体开源路线图
  53. 一篇文章帮你彻底搞清楚“I/O多路复用”和“异步I/O”的前世今生
  54. pytorch实现yolov3(1) yolov3基本原理
  55. 【Web前端Talk】React-loadable 进行代码分割的基本使用
  56. Java入门第73课——String常量池
  57. Java入门第74课——获取String对象的长度
  58. 学位服加入中式元素遭吐槽像寿衣 设计方:照片光线问题,衣服没问题
  59. 1005 继续(3n+1)猜想(C#)
  60. ARM A57/A72/A76架构之父跳槽苹果:A系列处理器将变更强
  61. SpringCloud系列——TX-LCN分布式事务管理
  62. 高考报考以及心态调整健康贴士
  63. cloudsim 3.0.3下载与安装教程
  64. 为什么很多人转化做web前端而不选择其他的呢?
  65. 记录一次关于Cookie、Json中文乱码的解决方法
  66. 定制虚拟币多币种钱包,ERC20币钱包开发
  67. 第9章 用户自己建立数据类型
  68. VsCode中编写python环境配置
  69. 考生被提醒不要用搜索引擎找填志愿网站 百度回应
  70. HTTP状态码
  71. 离航天飞机只差一步!“史上最难“猎鹰火箭发射究竟难在哪?
  72. 基建狂魔:7分钟车程挖13年!最难隧道终迎来重大突破
  73. 中国铁塔两子公司挂牌成立 可提供电动车换电服务
  74. 请你讲一讲JavaScript有哪些数据类型, 数据类型判断有哪些方法?
  75. 敏捷开发中如何做好Sprint规划?
  76. android 写文件到sd卡问题小记
  77. vue+element 获取验证码
  78. 关于《java多线程核心编程技术》中小节“将任意对象作为对象监视器”的错误
  79. 【算法随记三】小半径中值模糊的急速实现(16MB图7.5ms实现) + Photoshop中蒙尘和划痕算法解读。
  80. 20年研发管理经验谈(十二)
  81. 权威机构学者:比特币只是一种网络游戏,是庞氏骗局、郁金香泡沫的升级版
  82. SpringCloud学习(SPRINGCLOUD微服务实战)一
  83. vue+TS(CLI3)
  84. 华为胡厚崑:鸿蒙系统没推出时间表 华为是安卓坚定支持者
  85. 【Python基础】循环嵌套
  86. k近邻算法之kd树优化(kd树的构造和搜索)——基于Python
  87. 美国小型电信运营商与诺基亚爱立信讨论替换华为设备
  88. Python基础(六) 函数
  89. JavaScript规定了几种语言类型?
  90. JS数据结构第三篇---双向链表和循环链表之约瑟夫问题
  91. 几个高逼格 Linux 命令!
  92. RS232
  93. C++中调用OC代码
  94. OPPO展示两大"黑科技":屏下摄像头和无网络通信
  95. TDD(测试驱动开发)死了吗?
  96. 华为被禁国内手机销量大增 胡厚崑感谢国民的情感支持
  97. 全球养猪业震荡:非洲猪瘟洗牌,谁喜谁忧?|《财经》特报
  98. 采用透视全景屏 OPPO屏下摄像头手机发布
  99. UNIX环境高级编程(第3版)
  100. 在mybatis中调oracle dblink存储过程