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

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

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

作者 | 程序员小吴

来源 | 五分钟学算法

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

题目描述

有一个有序表为 {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

找到啦!

以上,便是今日分享,觉得不错,还请点个在看,谢谢~
推荐阅读:
有了这套模板,女朋友再也不用担心我刷不动 LeetCode 了
图解 LeetCode 第 421 题:数组中两个数的最大异或值
互联网人职业发展之路:三年升高工,七年做架构,十年送外卖

我的个人博客大改版啦,欢迎点击阅读原文进行访问~

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

原文始发于微信公众号(五分钟学算法)

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 五分钟学算法之经典算法题:二分查找

我还会在以下平台发布内容

GitHub 哔哩哔哩