{"blocks":[{"type":"header3","data":{"level":3,"text":"Условие задачи"}},{"type":"paragraph","data":{"text":"Имеется отсортированный массив из n целых чисел, который был циклически сдвинут неизвестное число раз. Напишите код для поиска элемента в массиве. Предполагается, что массив изначально был отсортирован по возрастанию."}},{"type":"paragraph","data":{"text":"Пример:
Ввод: найти 5 в {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}.
Вывод: 8 (индекс числа 5 в массиве)."}},{"type":"header3","data":{"level":3,"text":"Решение"}},{"type":"paragraph","data":{"text":"Если у вас возникла мысль о бинарном поиске, вы правы!"}},{"type":"paragraph","data":{"text":"В классической задаче бинарного поиска х сравнивают с центральной точкой, чтобы узнать, где находится х — слева или справа. Сложность в нашем случае заключается в том, что массив был циклически сдвинут, а значит, может иметь точку перегиба. Рассмотрим, например, два следующих массива:"}},{"type":"code","data":{"code":"Arrayl : {10, 15, 20, 0, 5}\r\nArray2 : { 50, 5, 20, 30, 40}","language":"java lazy-code"}},{"type":"paragraph","data":{"text":"У обоих массивов есть средняя точка – 20, но в первом случае 5 находится справа от нее, а в другом – слева. Поэтому сравнения х со средней точкой недостаточно. Однако если разобраться поглубже, можно заметить, что половина массива упорядочена нормально (то есть по возрастанию). Следовательно, мы можем рассмотреть отсортированную половину массива и решить, где именно следует производить поиск – в левой или правой половине."}},{"id":"56959227-1cae-4764-b396-893b3096423e","type":"banner-blank","data":{}},{"type":"paragraph","data":{"text":"Например, если мы ищем 5 в Array1, то посмотрим на крайний левый элемент (10) и средний элемент (20). Так как 10 < 20, становится понятно, что левая половина отсортирована. Поскольку 5 не попадает в этот диапазон, мы знаем, что искомое место находится в правой половине массива."}},{"type":"paragraph","data":{"text":"В Array2 мы видим, что 50 > 20, а значит, отсортирована правая половина. Мы обращаемся к середине (20) и крайнему правому элементу (40), чтобы проверить, попадает ли 5 в рассматриваемый диапазон. Значение 5 не может находиться в правой части, а значит, его нужно искать в левой части массива."}},{"type":"paragraph","data":{"text":"Задача становится более сложной, если левый и средний элементы идентичны, как в случае с массивом {2, 2, 2, 3, 4, 2}. В этом случае можно выполнить сравнение с правым элементом и, если он отличается, ограничить поиск правой половиной. В противном случае выбора не остается, и придется анализировать обе половины."}},{"type":"code","data":{"code":"public class Question {\r\n\t\r\n\tpublic static int search(int a[], int x) {\r\n\t\treturn search(a, 0, a.length - 1, x);\r\n\t}\r\n\r\n\t\r\n\tpublic static int search(int a[], int left, int right, int x) {\r\n\t\tint mid = (left + right) / 2;\r\n\t\tif (x == a[mid]) { // Элемент найден\r\n\t\t\treturn mid;\r\n\t\t}\r\n\t\tif (right < left) {\r\n\t\t\treturn -1;\r\n\t\t}\r\n\t\t\r\n\t\t/* Либо левая, либо правая половина должна быть нормально упорядочена .\r\n * Найти нормально упорядоченную сторону, а затем использовать ее\r\n * для определения стороны, в которой следует искать х. */\r\n\t\tif (a[left] < a[mid]) { // Левая половина нормально упорядочена .\r\n\t\t\tif (x >= a[left] && x < a[mid]) { \r\n\t\t\t\treturn search(a, left, mid - 1, x);// Искать слева\r\n\t\t\t} else {\r\n\t\t\t\treturn search(a, mid + 1, right, x);// Искать справа\r\n\t\t\t}\r\n\t\t} else if (a[mid] < a[left]) { // Правая половина нормально упорядочена.\r\n\t\t\tif (x > a[mid] && x <= a[right]) {\r\n\t\t\t\treturn search(a, mid + 1, right, x); // Искать справа\r\n\t\t\t} else {\r\n\t\t\t\treturn search(a, left, mid - 1, x); // Искать слева\r\n\t\t\t}\t\t\t\t\r\n\t\t} else if (a[left] == a[mid]) { // Левая половина состоит из повторов\r\n\t\t\tif (a[mid] != a[right]) { // Если правая половина отличается, искать в ней\r\n\t\t\t\treturn search(a, mid + 1, right, x);// Искать справа\r\n\t\t\t} else { // Иначе искать придется в обеих половинах\r\n\t\t\t\tint result = search(a, left, mid - 1, x); // Искать слева\r\n\t\t\t\tif (result == -1) {\r\n\t\t\t\t\treturn search(a, mid + 1, right, x); // Искать справа\r\n\t\t\t\t} else {\r\n\t\t\t\t\treturn result;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn -1;\r\n\t}\r\n\r\n\tpublic static void main(String[] args) {\r\n\t\tint[] a = { 2, 3, 1, 2, 2, 2, 2, 2 , 2 , 2 };\r\n\r\n\t\tSystem.out.println(search(a, 2));\r\n\t\tSystem.out.println(search(a, 3));\r\n\t\tSystem.out.println(search(a, 4));\r\n\t\tSystem.out.println(search(a, 1));\r\n\t\tSystem.out.println(search(a, 8));\r\n\t}\r\n\r\n}","language":"java lazy-code"}},{"type":"paragraph","data":{"text":"Код выполняется за время O(log n), если все элементы будут разными (об оценке сложности алгоритмов вы можете прочитать в нашей статье). При большом количестве дубликатов алгоритм потребует времени O(n). Это объясняется тем, что при большом количестве дубликатов часто приходится обрабатывать обе половины массива (левую и правую)."}},{"id":"b80bea77-8701-44ba-8dce-e9c41ddc2eb3","type":"banner-blank","data":{}},{"type":"paragraph","data":{"text":"Концептуально данная задача несложна, но написать идеальную реализацию достаточно трудно. Не беспокойтесь, если вы допустите пару-тройку ошибок при решении этой задачи. Из-за высокого риска смещения на 1 и других второстепенных ошибок код необходимо тщательно протестировать."}},{"type":"paragraph","data":{"text":"Также вы можете попробовать реализовать алгоритм поиска элемента в отсортированной матрице размером MxN. Решение найдете здесь."}}]}

Ошибка в настройках сайта