Временная сложность для вставки массива

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). Может ли кто-нибудь помочь мне с изменениями в функции, так что это может быть в о (журнал N).

Answer 1

Нет.

Этот код повторяется (наихудший случай) по всем значениям в массиве. Если значения вставляются случайным образом, точка вставки будет в среднем находиться в середине массива. Ты не break цикл, когда вы находите местоположение, как указывает @LukeLee, так что вы всегда будете перебирать все возможные местоположения - все N из них.

Чтобы достичь производительности O(logN), вам придется пропустить множество сравнений. Посмотрите на двоичный поиск, если ваш массив упорядочен.