java在数组中查找第一个索引值大于0（1）中的x

Question

我有一个int类型的排序数组，我想得到第一个索引，它的值大于java中O（1）中的目标值

例如：int-arr[]={1,4,7,9,15,30} 目标=10 我的函数应该返回4，索引为15

Answer 1

如果你准备了这样的索引数组（或映射）

    int[] a = {1,4,7,9,15,30};
    // prepare indices array
    int[] indices = new int[a[a.length - 1] + 1];
    for (int i = 0, j = 0, aLength = a.length; i < aLength; ++i)
        while (j <= a[i])
            indices[j++] = i;
    System.out.println(Arrays.toString(indices));
    // -> [0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
    // get the first index whose value is greater than a target in O(1)
    System.out.println(indices[10]); // -> 4 (index of 15)

你可以通过O（1）中的indices[target]得到索引值

Answer 2

为了能够通过数组找到具有特定属性（例如：大于目标）的值的索引，必须遍历实现搜索算法的数组

因此O（1）是不可能实现的

• 如果数组已排序，正如您在示例中所展示的那样，您可以通过实现二进制搜索算法来实现O（log（n））中所需的内容。您也可以使用^{}中的实现
• 如果数组未排序，则必须使用O（n）复杂度的线性搜索算法在最坏情况下遍历数组的所有元素