首页 > 试题广场 >

广告系统为了做地理位置定向，将IPV4分割成627672个区

[单选题]
广告系统为了做地理位置定向，将IPV4分割成627672个区间，并标识了地理位置信息，区间之间无重叠，用二分查找将IP地址映射到地理位置信息，请问在最坏的情况下，需要查找多少次？ 
  • 17
  • 18
  • 19
  • 20
添加回答
推荐
白驹之过隙头像 白驹之过隙
选D。该题考察的是二分查找原理（有序数列为前提）。
二分查找法的时间复杂度：O(logn)
如下图对有序序列进行二分法查找：10  12  13  15  17  19   假如查找15
  1. 索引low=0,high=5;中间数值mid为(low+high)/2=2对应13<15，所以继续在右半部份查找
  2. 索引low=mid+1=3，high=5;mid=4对应17>15，所以继续左边查找
  3. 索引low=3，high=mid-1=3;mid=3对应的15，正是要查找的元素。
所以最坏的情况下需要查找log(6)+1，根据结构类比的数学方法，log(627672)+1=20

编辑于 2019-07-09 14:08:16 回复(1)
wwwwxxxx头像 wwwwxxxx
627672 ＞ 2∧19 && 627672 ＜ 2∧20
发表于 2019-10-09 02:57:08 回复(0)
Master_Chef头像 Master_Chef

答案选择：

我们知道，二分查找的次数为。

其中表示对下取整，如,,。

在这一题中，我们需要在个数中查找一个数，因此答案就为。

这里给出输出的代码片段。 

cout << log(m) / log(n) << endl;

因此，我们只需要输出即可。

运行结果：
图片说明

因此，答案为

故答案为：

编辑于 2019-07-08 15:43:17 回复(0)
改个名求offer头像 改个名求offer
D
解析：二分查找的时间复杂度为O(logn)，故计算log627672即可，计算机默认是以2为底的对数，计算可得20。
发表于 2019-07-08 15:23:54 回复(0)
pythonicHuo头像 pythonicHuo

log2(627672)+1


发表于 2020-04-14 18:51:36 回复(0)
提交观点

问题信息

查找
上传者：牛100
难度：
5条回答 2122浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号