Двоичный поиск в массиве, в котором отсортированы все элементы, кроме двух, т.е. все элементы отсортированы, а затем два смежных элемента поменялись местами?

Question

Можно ли выполнить бинарный поиск в массиве, в котором сначала сортируются все элементы, а после этого чередуются два смежных элемента (из отсортированного массива)?

пример 3 10 40 20 50 70 80

В этом примере 20 и 40 поменялись местами.

Answer 1

Да, двоичный поиск может быть выполнен по этому типу массива.Идея для этого является чем-то похожим на бинарный поиск в повернутом отсортированном массиве - https://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/

Предположим, вам нужно искать 40 в этом -

• После 1-й итерации {3 10 40 2050 70 80} -> {3 10 40 20} и {50 70 80}.При разделении этого массива вам понадобятся граничные условия.В этом случае необходимо проверить, существует ли 40 во 2-м подмассиве.
• 2-я итерация.-> {3 10 40 20} -> {3,10} {40,20}.То же самое граничное условие должно быть применено в случае первого подмассива здесь.