Задача на поиск элемента в массиве

Условие задачи

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

Пример:
Ввод: найти 5 в {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}.
Вывод: 8 (индекс числа 5 в массиве).

Решение

Если у вас возникла мысль о бинарном поиске, вы правы!

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

			Arrayl : {10, 15, 20, 0, 5}
Array2 : { 50, 5, 20, 30, 40}
		

У обоих массивов есть средняя точка – 20, но в первом случае 5 находится справа от нее, а в другом – слева. Поэтому сравнения х со средней точкой недостаточно. Однако если разобраться поглубже, можно заметить, что половина массива упоря­дочена нормально (то есть по возрастанию). Следовательно, мы можем рассмотреть отсортированную половину массива и решить, где именно следует производить поиск – в левой или правой половине.

Например, если мы ищем 5 в Array1, то посмотрим на крайний левый элемент (10) и средний элемент (20). Так как 10 < 20, становится понятно, что левая половина отсортирована. Поскольку 5 не попадает в этот диапазон, мы знаем, что искомое место находится в правой половине массива.

В Array2 мы видим, что 50 > 20, а значит, отсортирована правая половина. Мы обращаемся к середине (20) и крайнему правому элементу (40), чтобы проверить, по­падает ли 5 в рассматриваемый диапазон. Значение 5 не может находиться в правой части, а значит, его нужно искать в левой части массива.

Задача становится более сложной, если левый и средний элементы идентич­ны, как в случае с массивом {2, 2, 2, 3, 4, 2}. В этом случае можно вы­полнить сравнение с правым элементом и, если он отличается, ограничить поиск правой половиной. В противном случае выбора не остается, и придется анализировать обе половины.

			public class Question {
	
	public static int search(int a[], int x) {
		return search(a, 0, a.length - 1, x);
	}

	
	public static int search(int a[], int left, int right, int x) {
		int mid = (left + right) / 2;
		if (x == a[mid]) { // Элемент найден
			return mid;
		}
		if (right < left) {
			return -1;
		}
		
		/* Либо левая, либо правая половина должна быть нормально упорядочена .
                 * Найти нормально упорядоченную сторону, а затем использовать ее
                 * для определения стороны, в которой следует искать х. */
		if (a[left] < a[mid]) { // Левая половина нормально упорядочена .
			if (x >= a[left] && x < a[mid]) { 
				return search(a, left, mid - 1, x);// Искать слева
			} else {
				return search(a, mid + 1, right, x);// Искать справа
			}
		} else if (a[mid] < a[left]) { // Правая половина нормально упорядочена.
			if (x > a[mid] && x <= a[right]) {
				return search(a, mid + 1, right, x); // Искать справа
			} else {
				return search(a, left, mid - 1, x); // Искать слева
			}				
		} else if (a[left] == a[mid]) { // Левая половина состоит из повторов
			if (a[mid] != a[right]) { // Если правая половина отличается, искать в ней
				return search(a, mid + 1, right, x);// Искать справа
			} else { // Иначе искать придется в обеих половинах
				int result = search(a, left, mid - 1, x); // Искать слева
				if (result == -1) {
					return search(a, mid + 1, right, x); // Искать справа
				} else {
					return result;
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] a = { 2, 3, 1, 2, 2, 2, 2, 2 , 2 , 2 };

		System.out.println(search(a, 2));
		System.out.println(search(a, 3));
		System.out.println(search(a, 4));
		System.out.println(search(a, 1));
		System.out.println(search(a, 8));
	}

}
		

Код выполняется за время O(log n), если все элементы будут разными (об оценке сложности алгоритмов вы можете прочитать в нашей статье). При большом количестве дубликатов алгоритм потребует времени O(n). Это объясняется тем, что при большом количестве дубликатов часто приходится обрабатывать обе половины массива (левую и правую).

Концептуально данная задача несложна, но написать идеальную реализацию до­статочно трудно. Не беспокойтесь, если вы допустите пару-тройку ошибок при решении этой задачи. Из-за высокого риска смещения на 1 и других второстепенных ошибок код необходимо тщательно протестировать.

Также вы можете попробовать реализовать алгоритм поиска элемента в отсортированной матрице размером MxN. Решение найдете здесь.