Источник: Карьера программиста
Условие задачи
Имеется отсортированный массив из 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. Решение найдете здесь.
