首页 > 试题广场 > 广告系统为了做地理位置定向,将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)
627672 > 2∧19 && 627672 < 2∧20
发表于 2019-10-09 02:57:08 回复(0)

答案选择:

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

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

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

这里给出输出代码片段。

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

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

运行结果:
图片说明

因此,答案为

故答案为:

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