Написано: 09.03.2023

34. Найти первую и последнюю позицию элемента в отсортированном массиве (Find First and Last Position of Element in Sorted Array)

medium

Задание.

Получен массив целых чисел nums, отсортированных в порядке неубывания.

Нужно найти начальную и конечную позиции заданного target.

Если в nums нет target, нужно вернуть [-1,-1]

Нужно написать алгоритм со сложностью времени выполнения O(log n).

Пример 1.

Входные данные: nums = [5,7,7,8,8,10], target = 8

Результат: [3,4]

Пример 2.

Входные данные: nums = [5,7,7,8,8,10], target = 6

Результат: [-1,-1]

Пример 3.

Входные данные: nums = [], target = 0

Результат: [-1,-1]

Решение.

class Solution {
private:
    int findOccur(vector<int>& nums, int target, bool first)
    {
        int size = nums.size();
        int s = 0, e = size-1, m;
        int index = -1;
        while(s <= e) {
            m = s + (e-s)/2;
            if(nums[m] == target) {
                index = m;
                if(first == true) {
                    e = m-1;
                } else {
                    s = m+1;
                }
            } else if(nums[m] > target) {
               e = m-1;
            } else {
               s = m+1;
            }
        }

        return index;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> v;
        int firstOccur, lastOccur = -1;
        if((firstOccur = findOccur(nums, target, true)) != -1) {
            lastOccur = findOccur(nums, target, false);
        }
        v.push_back(firstOccur);
        v.push_back(lastOccur);
        return v;
    }
};