在O(1)中查找数组值大于x的第一个索引

Question

我有一个int类型的排序数组.我想在java中获取第一个索引,其值大于O(1)中的目标.

例如:int arr [] = {1,4,7,9,15,30} target = 10我的函数应返回4,索引为15.

Answer 1

为了能够通过数组找到具有特定属性(例如:大于目标)的值的索引,您必须遍历实现搜索算法的数组.

因此O(1)是不可能实现的.

• 如果对数组进行排序,正如您在示例中所示,您可以通过实现二进制搜索算法在O(log(n))中实现所需的数据.您也可以使用该实现java.util.Arrays.
• 如果数组未排序,则必须在最坏情况下使用具有O(n)复杂度的线性搜索算法遍历数组的所有元素.