algorithm - 寻找具有 o-small(n) 复杂度的第一个较大整数的算法

Question

我需要编写一个算法，它将在排序数组中找到第一个大于 x 的整数，其中整数可能重复。该算法应该具有 o(n) 的复杂度，其中 o 很小。O(n) 和 o(n) 难度的算法有什么区别？

标签： algorithmbig-o

Answer 1

您可以使用二分查找方法找到 的第一个最大整数x。它会在O(log(n)) = small_o(n).