Поиск элемента в отсортированном массиве, сформированном путем реверсирования подмассивов из случайного индекса

Учитывая отсортированный массив arr[] размера N и целочисленный ключ, задача состоит в том, чтобы найти индекс, по которому ключ присутствует в массиве. Данный массив получен путем перестановки подмассивов {arr[0], arr[R]} и {arr[R + 1], arr[N – 1]} по некоторому случайному индексу R. Если ключ отсутствует в массиве массив, напечатать -1 .

Примеры:

Input: arr[] = {4, 3, 2, 1, 8, 7, 6, 5}, key = 2
Output: 2

Input: arr[] = {10, 8, 6, 5, 2, 1, 13, 12}, key = 4
Output: -1

Наивный подход: самый простой подход к решению проблемы — пройтись по массиву и проверить, присутствует ли ключ в массиве или нет. Если найдено, то распечатать индекс. В противном случае выведите -1.

Временная сложность: O(N)
Вспомогательное пространство: O(1)

Эффективный подход. Чтобы оптимизировать описанный выше подход, идея состоит в том, чтобы применить модифицированный двоичный поиск к массиву для поиска ключа . Выполните следующие шаги, чтобы решить эту проблему:

• Инициализируйте l как 0 и h как N – 1, чтобы сохранить индексы граничных элементов пространства поиска для бинарного поиска.
• Итерировать, пока l меньше или равно h:
  • Сохраните среднее значение в переменной mid как (l+h)/2 .
  • Если arr[mid] равно key , затем напечатайте mid как ответ и вернитесь.
  • Если arr[l] больше или равно arr[mid] , это означает, что случайный индекс находится справа от mid .
    • Если значение ключа находится между arr[mid] и arr[l] , обновите h до mid-1 .
    • В противном случае обновите l до mid+1.
  • В противном случае это означает, что случайная точка лежит слева от середины .
  • Если значение ключа находится между arr[h] и arr[mid], обновите l до mid+1.
  • В противном случае обновите h до mid-1 .
• Наконец, выведите -1 , если ключ не найден.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log (N))
Вспомогательное пространство: O(1)