Что такое повернутый отсортированный массив?

Рассмотрим отсортированный массив, например:

[1, 2, 3, 4, 5, 6]

Теперь, если этот массив повернуть в какой-либо опорной точке, скажем, в индексе 3, он будет выглядеть так:

[4, 5, 6, 1, 2, 3]

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

Стратегия поиска

Для поиска в повернутом отсортированном массиве нам необходимо:

1. Найти ось: ось — это точка, в которой массив переходит от больших значений к меньшим.
2. Двоичный поиск: как только мы найдем опорную точку, мы можем использовать двоичный поиск в соответствующей половине массива.

Пошаговое объяснение кода

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: "   result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot   1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start  arr[mid   1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] 







  
  
  Пояснение Кодекса




поиск():


Эта функция отвечает за поиск цели в отсортированном массиве.
Сначала мы находим центр с помощью функции searchPivot().
В зависимости от положения точки поворота мы затем решаем, в какой половине массива выполнять поиск с помощью двоичного поиска.



binarySearch():


Стандартный алгоритм двоичного поиска для поиска цели в отсортированном подмассиве.
Мы определяем начальный и конечный индексы и постепенно сужаем пространство поиска.



searchPivot():


Эта функция определяет точку поворота (место вращения массива).
Опорная точка — это индекс, в котором порядок сортировки «нарушен» (т. е. массив переходит от более высокого значения к меньшему).
Если опорная точка не найдена, это означает, что массив не был повернут, и мы можем выполнить обычный двоичный поиск.








  
  
  Как работает алгоритм


Для массива типа [4, 5, 6, 1, 2, 3]:

• Опорная точка находится под индексом 2 (6 – самый большой, за ним следует 1 – самый маленький).
• Мы используем эту опорную точку, чтобы разделить массив на две части: [4, 5, 6] и [1, 2, 3].
• Если цель больше или равна первому элементу (в данном случае 4), мы ищем левую половину. В противном случае мы ищем правую половину.

Этот метод гарантирует эффективность поиска, достигая временной сложности O(log n), аналогично стандартному двоичному поиску.

Заключение

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

Если эта статья оказалась для вас полезной, свяжитесь со мной в LinkedIn или поделитесь своими мыслями в комментариях! Приятного кодирования!