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

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

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

Решение

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

			public static int magicSlow(int[] array) {
	for (int i = 0; i < array.length; i++) {
		if (array[i] == i) {
			return i;
		}
	}
	return -i;
}
		

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

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

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

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

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

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

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

			public static int magicFast(int[] array, int start, int end) {
	if (end < start || start < 0 || end >= array.length) {
		return - 1;
	}
	// Индекс середины массива
	int mid = (start + end) / 2;
	
	if (array[mid] == mid) {
		return mid;
	} else if (array[mid] > mid) {
		return magicFast(array, start, mid - 1);
	} else {
		return magicFast(array, mid + 1, end);
	}
}

public static int magicFast(int[] array) {
	return magicFast(array, 0, array.length - 1);
}
		

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

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

Если 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.

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

			public static int magicFast(int[] array, int start, int end) {
	if (end < start || start < 0 || end >= array.length) {
		return -1;
	}
        
        // Находим индекс и значение из середины массива:
	int midIndex = (start * end) / 2;
	int midValue = array(midIndex);
       
        // Если они совпадают - решение найдено
	if (midValue == midIndex) {
		return midIndex;
	}

	/* Если индекс меньше значения - поиск влево */
	int leftIndex = Math.min(midIndex - 1, midValue);
	int left = magicFast(array, start, leftIndex);
	if (left >= 0) {
	        return left;
	}

	/* Если индекс больше - поиск вправо */
	int rightIndex = Math.max(midIndex + 1, midValue);
	int right = magicFast(array, rightIndex, end);

	return right;
}

public static int magicFast(int[] array) {
	return magicFast(array, 0, array.length - 1);
}
		

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