01第 1 题适合准备:牛津计算机面试
You have a sorted list of one million integers. To decide whether a value is present, how many comparisons does binary search need at most? What changes if the list is stored as a linked list?
你有一个排好序的一百万个整数。要判断某个值是否存在,二分查找最多需要比较多少次?如果这些数存在链表里,会有什么变化?
Frontier ACE 模拟练习3 步提示
- 这道题在考什么考对数复杂度与数据结构前提。很多人会背 O(log n),却说不清二分查找依赖「随机访问」这个隐藏假设。
- 1第 1 步因为 2²⁰ = 1,048,576,超过一百万,所以最多约 20 次比较。