Учитывая массив целых чисел, отсортированных в порядке возрастания, найдите начальную и конечную позиции заданного целевого значения.

Сложность выполнения вашего алгоритма должна быть порядка O (log n).

Если цель не найдена в массиве, верните [-1, -1].

Пример 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Пример 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Это проблема с leetcode: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Решение:

Подход 1:

Сложность времени: O (n)

Космическая сложность: O (1)

В этом подходе мы сначала возьмем две переменные firstIndex и lastIndex. Мы будем перебирать массив с самого начала. Найдя элемент target, мы обновим как firstIndex, так и lastIndex.

Теперь у нас есть первое вхождение, но нам все еще нужно найти последнее вхождение. Мы продолжим перебирать массив и обновлять lastIndex, пока не встретим элемент target.

Например, у нас есть массив [1,2,4,6,8,8,8,8,8,8,9,10,11], а цель - 8.

Теперь мы начнем итерацию с нулевого индекса. В четвертом индексе мы встретим 8, поэтому firstIndex будет 4, а lastIndex также будет 4. Теперь мы продолжим итерацию массива, и пока мы не встретим 8 в массиве, мы будем продолжать увеличивать lastIndex.

Ниже приведено решение этой проблемы на языке Java:

package com.ds.arrays;
public class FirstAndLastPosition {
    public static int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = -1;
        result[1] = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (result[0] == -1) {
                    result[0] = i;
                    result[1] = i;
                } else {
                    result[1] = i;
                }
            }
        }
        return result;
    }  
   
}

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

Подход 2:

Сложность времени: O (log (n))

Космическая сложность: O (1)

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

Работа бинарного поиска

Предположим, у меня есть отсортированный массив (помните, что двоичный поиск работает только для отсортированных массивов), который содержит 20 элементов.

int [] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

Теперь, если нам нужно найти 20 в этом массиве и мы используем линейный поиск, нам придется начинать с начала, пока мы не дойдем до конца и не найдем 20 в последней позиции. Таким образом, нам потребуется 20 сравнений, прежде чем мы получим наш результат.

Вместо этого в двоичном поиске мы продолжаем делить массив от середины, пока не найдем число. В приведенном выше примере число 20 можно найти только в 4 сравнениях. Ниже представлена ​​работа бинарного поиска:

Изначально предположим, что у нас есть три переменные start, end и mid.

Формула для вычисления mid = start + ((end - start) / 2)

Сравнение 1: начало - 0, конец - 20, а середина - 10. nums [mid] равно 11, что равно ‹target (20), поэтому start станет mid + 1, то есть 11.

Сравнение 2: начало - 11, конец - 20, а середина - 15. nums [mid] равно 16, что равно ‹target (20), поэтому start станет mid + 1, то есть 16.

Сравнение 3: начало - 16, конец - 20, а середина - 18. nums [mid] равно 19, что равно ‹target (20), поэтому start станет mid + 1, то есть 19.

Сравнение 4: начало - 19, конец - 20, а середина - 19. nums [mid] равно 20, что равно target (20), поэтому мы получили результат.

Как видите, мы получили результат только в 4-х сравнениях. Это сила двоичного поиска, и мы всегда должны пытаться использовать ее, если у нас есть отсортированный массив.

Теперь переходим к нашей основной задаче поиска первой и последней позиции. Ниже приведен код Java для решения этой проблемы с помощью двоичного поиска.

package com.ds.arrays;
public class FirstAndLastPosition {
    public static int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = -1;
        result[1] = -1;
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + ((end - start) / 2);
            if (nums[mid] == target) {
                result[0] = findStart(nums, start, mid, target);
                result[1] = findEnd(nums, mid, end, target);
                return result;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return result;
    }
    public static int findStart(int[] nums, int start, int end, int target) {
        int result = end;
        while (start <= end) {
            int mid = start + ((end - start) / 2);
            if (nums[mid] == target) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return result;
    }
    public static int findEnd(int[] nums, int start, int end, int target) {
        int result = start;
        while (start <= end) {
            int mid = start + ((end - start) / 2);
            if (nums[mid] == target) {
                result = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return result;
    }
}