首页 > 试题广场 >

有一个有序表位{1,3,9,12,32,41,45,62,7

[单选题]
有一个有序表位{1,3,9,12,32,41,45,62,75,77,82,95,99},当采用二分查找法查找关键字为82的元素时,()次比较后查找成功。
  • 1
  • 2
  • 4
  • 8
log2(13)=4(向上取整)
4是平均查找时间。
可以排除的选项只有d

计算 第1234步比较的分别是 45 77 95 82

编辑于 2020-06-04 10:34:15 回复(0)
直接用log2(13)向上取整数 4
发表于 2019-02-26 08:49:47 回复(2)
int[] numbers = {1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 99}
  1. len = 13, low = 0, high = 12, mid = (0 + 12) >>> 1 = 6, 45 < target = 82。
  2. low = mid + 1, low => 7, high = 12, mid = (low + high) >>> 1 = 9, 77 < target = 82。
  3. low = mid + 1, low => 10, high = 12, mid = (low + high) >>> 1 = 11, 95 > target = 82。
  4. high = mid - 1 = 10, mid = (low + high) >>> 1 = 10, find 82。

查找具体过程如上。

发表于 2018-05-28 20:29:43 回复(0)
依次比较的元素为45,77,95,82
发表于 2018-05-08 14:13:01 回复(0)
🍉与45比较,45<82,low=mid +1 🍉与77比较,77<82,low=mid+1 🍉与95比较,95>82,high=mid-1, 此时low和high指针都指向82 🍉与82比较,82=82,比较完成。
编辑于 2021-11-29 17:02:13 回复(0)
从中间开始都比82小,怎么会有95呢?
发表于 2020-08-24 09:34:19 回复(0)
不是向上取整吗,为啥我算2次就够了
发表于 2020-07-18 21:40:44 回复(1)
45,77,95,82
发表于 2020-05-11 13:17:22 回复(0)
查找
发表于 2019-09-16 01:06:51 回复(0)

def binary_search(find, L) :
  low = 0
  high = len(L)
  while low < high :
    mid = int((low + high) / 2)
    print(L[mid])
    if L[mid] == find :
      return "目标位置为:%d" % mid
    elif L[mid] > find :
      high = mid - 1
    else :
      low = mid + 1
  return -1
 
L = [1,3,9,12,32,41,45,62,75,77,82,95,99]
result = binary_search(82, L)
print(result)
只用两次就可以了啊,45,82

编辑于 2018-08-23 17:07:44 回复(4)