首页 > 试题广场 >

使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为？

[单选题]
使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为（ ） 
  • O(N)
  • O(logN)
  • O(N*N)
  • O(N*logN)
添加回答
推荐
牛客-007头像 牛客-007
答案：B
二分查找又称折半查找，时间复杂度是对数级的，O(logN)
编辑于 2015-09-05 13:21:12 回复(0)
manhua头像 manhua
折半查找，每次都是1/2,设寻找t次，等式为2t =n,n为数据的总数，倒过来就答案B。
发表于 2015-09-05 16:58:34 回复(0)
璎珞-沐头像 璎珞-沐
时间复杂度无非就是while循环的次数！
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1 
可得k=log2n,（是以2为底，n的对数）

发表于 2017-03-11 11:27:17 回复(0)
等一下，我的offer呢？头像 等一下，我的offer呢？

第一次，在  个中找

第二次，在  个中找

第三次，在  个中找

.
.
.

第 k 次，在  个中找

假设在第 k 次找到了，则 

故 ，

每次执行一次，一共执行 k 次，则 

注意：每一次查找的行为，可以放在循环中，也可以放在函数中，即递归。
发表于 2020-09-19 19:49:20 回复(0)
HonestFox头像 HonestFox
概念不清楚也可以排除
既然是查找 时间复杂度肯定不可能大于N吧 
二分又比普通遍历（O(N)）快  所以 只能选B咯
发表于 2016-08-16 23:43:52 回复(0)
心系蝶相印头像 心系蝶相印

1.     顺序查找，时间复杂度为O(n)

2.     二分查找，时间复杂度为O(log2n)

3.     插值查找，关键字分布又比较均匀, 时间复杂度为O(log2(log2n))

4.     斐波那契查找，时间复杂度为O(log2n)

5.     树表查找

a)     二叉树查找算法，插入和查找的时间复杂度均为O(logn)

b)     红黑树，logn

c)     B树和B+树，O(log n)

6.     分块查找，关键字构成一个索引表

7.      哈希查找，以空间换时间的算法

发表于 2018-04-01 19:20:35 回复(0)
Jevon123头像 Jevon123
🤣
发表于 2019-08-27 11:58:48 回复(0)
邓胜涛1头像 邓胜涛1
二分＝折半查找，公式O(log N)
编辑于 2018-11-30 09:13:36 回复(0)
pedro.z头像 pedro.z
(log2n)+1 => O(logn)
发表于 2018-08-15 22:34:05 回复(0)
大肥肥头像 大肥肥

对于一个排序好的的数组进行查找，时间复杂度为  O(lgn)

发表于 2016-04-14 09:05:56 回复(0)
提交观点

问题信息

查找
来自：腾讯2013研发工程师笔试题
上传者：若微蓝
难度：
10条回答 22010浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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