Какие числа меняются местами из отсортированного массива

Я не уверен, что полностью понимаю вопрос, в любом случае, если вы не знаете оба элемента, и поскольку обмен не имеет «правила». кажется, вам нужно как минимум o (n), чтобы найти замененный элемент. (простым циклом).

Если вы знаете один элемент (один из пары) и хотите найти другую пару. просто бинарный поиск одной пары, которую вы знаете, вы найдете другую на его месте.

Оказывается, единственный способ найти такой элемент — обычный линейный поиск. Вы не можете сделать быстрее, потому что вы в основном не ищете конкретный элемент, вы ищете позицию, когда какое-то свойство нарушается (в данном случае порядок). Поскольку вы не знаете ничего, что могло бы помочь вам пропустить проверку некоторых позиций, вам в основном нужно проверить их все. Так что это будет O(n) — обычный линейный поиск.

Вам нужно выполнять линейный поиск, а время наихудшего случая является линейным. Но в лучшем случае время может быть log n.

Как только вы найдете первый смещенный элемент, вы узнаете это целое число. Следовательно, вы можете выполнить бинарный спуск, чтобы найти положение, в котором он должен быть. Таким образом, если одно из двух несоответствий произойдет раньше, вы сэкономите время.