Задача на поиск «волшебного» индекса в массиве

В массиве случайных чисел A1 задан один «волшебный» индекс: такой, что A[i] = i. Значения элементов в массиве повторяться не могут. Учитывая, что массив отсортирован по значениям в порядке возрастания, напишите метод, который определит этот «волшебный» индекс, если он существует в массиве A. Если элемента в массиве нет, верните любое отрицательное число.

Дополнительно:
Как изменится решение, если известно, что таких индексов в массиве несколько?

Решение

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

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

Так задача становится похожа на классическую задачу бинарного поиска. Для алгоритма больше всего подходит способ «сопоставления с образцом».

При бинарном поиске мы берем элемент k и сравниваем его с элементом из середины массива, x, чтобы определить, по какую сторону от x находится искомого k — слева или справа. Давайте попробуем определить, где может находиться «волшебный» элемент на примере. Взгляните на массив (нижняя строка — индексы элементов):

-40-20-11235791213
012345678910

Если взять элемент из середины массива, A[5] = 3, то становится ясно, что «волшебный» элемент должен находиться правее, так как A[mid] < mid. Почему в этой ситуации элемент не может быть слева? Индекс элемента в данном случае уже больше значения (5 > 3). Значит, все значения элементов с индексами 0-4 будут меньше самих индексов.

При движении в направлении от i к i-1 значение элемента будет уменьшаться не менее чем на 1 (так как массив отсортирован и не содержит одинаковых элементов). Если средний элемент меньше искомого, то при движении влево, смещаясь на k индексов и (как минимум) на k значений, мы будем попадать на еще более маленькие значения.

Наш алгоритм будет по такому принципу выяснять, где должен находиться искомый элемент — справа или слева, и проверять только одну половину массива. Этим мы сокращаем число итераций, необходимых для того, чтобы наткнуться на нужный элемент.

При использовании рекурсивного решения алгоритм похож на бинарный поиск.

Дополнительно: как изменится решение, если таких индексов окажется несколько?

Если элементы массива повторяются, то наш алгоритм не будет работать. Давайте рассмотрим следующий массив:

-10-522234791213
012345678910

Если A[mid] < mid, сказать заранее, где будут находиться «волшебные» элементы, становится сложнее.

Могут ли в этом массиве они находиться слева? Нет. Так как A[5] = 3, мы знаем, что A[4] никак не может быть «волшебным» элементом. A[4] должен быть равен 4, но в то же время мы знаем, что A[4] не может быть больше, чем A[5], из-за условия отсортированности.

Фактически, если мы видим, что A[5] = 3, нам достаточно проанализировать только правую сторону, как это и делалось раньше. Но чтобы найти элемент в левой части, можно пропустить группу элементов и произвести поиск только среди A[0] ‒ A[3], где A[3] — это первый элемент, который может быть «волшебным».

В общем, нам нужно взять элемент из середины массива и сравнить его индекс с его же значением — midIndex с midValue. Если они совпадают, то возвращаем значение сразу. Иначе выясняем, больше или меньше значение элемента из середины его индекса. В зависимости от полученного результата начинаем искать либо слева, либо справа.

  • Левая сторона: поиск среди элементов от start до Math.min(midIndex - 1, midValue).
  • Правая сторона: поиск среди элементов от Math.Max(midIndex + 1, midValue) до end.

Если же переданы ошибочные параметры, пусть код возвращает -1.

Представленный ниже код реализует данный алгоритм:

Этот код работает в том числе и для случая без дополнительного условия.

  1. ..n-1

Взято из книги «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»