专栏首页五分钟学算法五分钟学算法之经典算法题:二分查找

五分钟学算法之经典算法题:二分查找

作者 | 程序员小吴

今天分享一道简单的笔试题,题目来源于京东校园招聘笔试真题。你做出这道简单的题目需要花费多少分钟呢?

题目描述

有一个有序表为 {1,5,8,11,19,22,31,35,40,45,48,49,50} ,当二分查找值为 48 的结点时,查找成功需要比较的次数( )

  • A、4
  • B、3
  • C、2
  • D、1

题目分析

一道送分题。

有序表的长度为 13,根据 二分查找法 查找数的特性,每次都 n/2 进行折半查找。

13 / 2 = 6
6 / 2 = 3
3 / 2 = 1
1 / 2 = 0

最多需要 4 次就能得出结果。

这道题目需要查找的是 48 ,列表下标索引从零开始标记。

第一次,求出 [0,12] 中间节点。

0 + (12 - 0) / 2 = 6 

a[6] = 31 < 48

区间变为 [7,12]。

第二次,求出 [7,12] 中间节点。

7 + (12 - 7) / 2 = 9 

a[9] = 45 < 48

区间变为 [10,12]。

第三次,求出 [10,12] 中间节点。

10 + (12 - 10) / 2 = 11 

a[11] = 49 > 48

区间变为 [10,11]。

第四次,求出 [10,11] 中间节点。

10 + (11 - 10) / 2 = 10

a[10] = 48 = 48

找到啦!

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 推荐一款让你纵横 Github 的读码神器

    通过 git clone 或 download 的方式,将项目源文件下载到本地,然后通过自己最顺手的 IDE 打开阅读。

    五分钟学算法
  • 拒绝遗忘:高效的动态规划算法

    假设你正在使用适当的输入数据进行一些计算。你在每个实例中都进行了一些计算,以便得到一些结果。当你提供相同的输入时,你不知道会有相同的输出。这就像你在重新计算之前...

    五分钟学算法
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    五分钟学算法
  • VHDL硬件描述语言(三)——基本数据对象和数据类型

    VHDL是一种强类型的语言,它不允许不同数据类型之间的相互赋值。如果想在不同数据类型之间进行赋值则需要调用函数来完成。

    zy010101
  • 性能测试-Jmeter之测试报告

    批量执行完接口测试之后,我们需要查看测试报告,在之前单个接口调试我们是通过查看结果树查看结果,但是当大批量执行接口测试之后依旧这样查看那么肯定会很低效 那么该如...

    用户6367961
  • dedecms批量导出新增文章url和标题

      百度站长工具推出主动提交功能有一段时间了,可以将新产出链接立即通过此方式推送给百度,以保证新链接可以及时被百度收录。那么dedecms如何批量导出新增文章u...

    ytkah
  • Git 远程推送被拒绝的一种解决方案

    skylark
  • Intellij IDEA调试功能使用总结

    这段时间一直在使用Intellij IDEA, 今天把调试区工具的使用方法记录于此。 先编译好要调试的程序。 1.设置断点 ? 选定要设置断点的代码行,在行号的...

    MonroeCode
  • Intellij IDEA调试功能使用总结

    专注于Java领域,追求简洁,每天推送高质量技术文章,实用教程。

    MonroeCode
  • 你有必要了解一下Flink底层RPC使用的框架和原理

    对于Flink中各个组件(JobMaster、TaskManager、Dispatcher等),其底层RPC框架基于Akka实现,本文着重分析Flink中的Rp...

    王知无

扫码关注云+社区

领取腾讯云代金券