查找大于给定数字的最小数字（访谈）

最近我被给了一个面试问题，说你有一个有序的数字列表（元素的数量可能相当大，约为100000），你会发现大于给定数字的最小数字表示在O（log n）时间内做到这一点的方法......我的第一个猜测是使用像面试官说的yes的数据结构之类的树，但是他们在建造这些树木时有一些开销我可以建议另一种方法？我明显的答案是使用数组进行二分搜索，虽然想知道这是否会工作，或者有其他的？查找大于给定数字的最小数字（访谈）

来源

2013-03-30 user1950055

[二进制搜索]（http://en.wikipedia.org/wiki/Binary_search_algorithm） –

是的，他们问你是否知道二分查找。 – zch

我认为二进制搜索是他们想要听到的。另一方面，如果不知道这个清单是如何组织的，那么真的不可能提供正确的建议。它可能是一个链表。非常有序，但显然没有随机访问成员。在这种情况下，不会比O（n）更快。 – mikyra

它取决于您正在使用的列表的类型。

如果它没有索引列表，那么O（logN）将不可能没有任何重组。

所以如果它是一个索引列表。

您可以按分割搜索。

比较所述目标与[N/2]

如果A [N/2]小于目标..搜索空间减小。从开始[N/2 + 1] .. A [N-1]

用同样的方法递归算法中，直到找到一对，使得[I] <目标< A [1 + 1]

这将是结束和[i + 1]是你的答案..！

来源

2013-03-30 23:09:20 MissingNumber

你的方法和排序+ OP提出的二分查找有什么区别？ – angelatlarge

是二进制搜索是我所建议的，但是想知道是否还有其他二进制搜索？ – user1950055

二进制搜索查找任何确切的数字。这是二进制搜索的相同方法，但不仅仅是找到确切的数字。 – MissingNumber

查找大于给定数字的最小数字（访谈）

回答

相关问题