java - 数组插入的时间复杂度

Question

我正在编写函数来查找应在给定数组中插入目标值的位置。我们假设数组具有不同的值并按升序排序。

这里我希望时间复杂度为 O(logN)。

public static int FindPosition(int[] Arr, int element)
{
    int i; int u=0;
    {
        for(i=0;i<Arr.length;i++)
        {
            if(element>Arr[i])
            u++;
        }
    }
    return u;
}

这个程序的时间复杂度是否为 O(log n)。任何人都可以帮助我更改功能，使其可以在o（log n）中。

Answer 1

不。

该代码迭代（最坏情况）数组中的所有值。如果值是随机插入的，则插入点将平均位于数组的中间。正如@LukeLee 指出的那样，当您找到位置时，您不会break循环，因此您将始终遍历每个可能的位置 - 所有 N 个。

为了获得 O(logN) 的性能，您将不得不跳过很多比较。如果您的数组是有序的，请查看二进制搜索。