从一个数组中查找元素，时间复杂度最低可以为：

[单选题]

查看正确选项

打工人想要双休

如果数组有序且用哈希表存储，不是能够做到查找效率为O(1)吗？

发表于 2025-02-16 19:29:15 回复(0)

牛客00__

运用二分查找，有两个指针l和r，每次都会更新出一个新的mid=(l+r)/2，若查找的数在mid左边，则r=mid-1；若在右边，则l=mid+1，有步骤可知，每次更新出一个mid，查找范围会少一半，因此时间复杂度为O(logn)，比如n=16，查找的数在1的位置（极端情况）：

初始，l=1，r=16。

更新出mid=8,判断得l=1，r=7。

更新出mid=4,判断得l=1，r=3。

更新出mid=2,判断得l=1，r=1。

更新出mid=1,判断得已经找出结果。

以上查找了4次，时间复杂度为O(4)，log16= $log_2$ 16=4，因此正确。

发表于 2024-11-09 21:19:47 回复(0)

一笑而过2222

# 在二分查找中，每次比较都能将查找范围缩小一半。 # 经过最多log₂n次比较就能找到目标元素或者确定目标元素不存在，所以时间复杂度为O(log n)。

发表于 2024-11-09 09:03:52 回复(0)

提交观点

问题信息

复杂度

来自：2023年4399游戏...

难度：

3条回答 14收藏 525浏览

扫一扫，把题目装进口袋