Сложность времени для операций поиска и вставки в отсортированных и несортированных массивах, включающих повторяющиеся значения

Question

1-) Для отсортированного массива я использовал Бинарный поиск. Мы знаем, что в худшем случае сложность операции SEARCH в отсортированном массиве равна O (lg N), если мы используем бинарный поиск, где N - количество элементов в массиве. Какова сложность наихудшего случая для операции поиска в массиве, который включает повторяющиеся значения, используя двоичный поиск? Это будет тот же O (LG N) ?? Пожалуйста, поправьте меня, если я ошибаюсь !!

Кроме того, каков наихудший случай для операции INSERT в отсортированном массиве с использованием бинарного поиска? Я думаю, O (N) .... это верно ??

2-) Для несортированного массива я использовал Линейный поиск. Теперь у нас есть несортированный массив, который также принимает повторяющиеся элементы / значения. Каковы наилучшие наихудшие сложности для операций поиска и вставки. Я думаю, что мы можем использовать линейный поиск, который даст нам O (N) наихудшее время для обоих поисков и удалить операции. Можем ли мы добиться большего успеха, чем это, для несортированного массива и изменить его сложность, если мы примем дубликаты в массиве.

Answer 1

1. Да.

2. Лучший случай неинтересен. (Подумайте, почему это может быть.) Худший случай - O (N), кроме вставок. Вставка в несортированный массив выполняется быстро, одна операция. (Опять же, подумайте об этом, если вы этого не видите.)

Как правило, дубликаты не имеют большого значения, за исключением крайне патологических распределений.

Answer 2

Мы можем улучшить удаление из неупорядоченного массива! Так как в этом случае порядок не имеет значения, мы можем поменять удаляемый элемент с последним, что поможет избежать ненужного смещения элементов в массиве. Таким образом удаляя в O (1) раз.

Answer 3

Некоторая помощь в пути - но не полное решение.

1. Наилучший случай для бинарного поиска, если искомый элемент является первым элементом поворота. Наихудший случай - когда нужно детально изучить два соседних элемента и все еще не найти то, что вы ищете. Изменится ли это, если в данных есть дубликаты? Вставка данных в отсортированный массив включает в себя перетаскивание всех данных с более высоким порядком сортировки «на один шаг вправо». В худшем случае вы вставляете элемент с более низким порядком сортировки, чем любой существующий элемент.
2. Поиск в несортированном массиве. Выбор не возможен, кроме линейного поиска, который вы предлагаете сами. Если вам не важен порядок сортировки, есть гораздо более быстрый и простой способ выполнить вставку. Удалить можно рассматривать как сначала поиск, а затем удаление.