План курса / Все задачи / Алгоритмы и структуры данных

Поиск первой и последней позиции

средне

# решено

Дан массив nums, отсортированный в неубывающем порядке, и число target. Нужно вернуть начальную и конечную позицию числа target в массиве nums. Если число target отсутствует, вернуть [-1, -1].

Пример 1:

Ввод: nums = [1,2,2,2,2,2,5,5,8,19], target = 2
Вывод: [1,5]
Объяснение: индексация элементов начинается с нуля

Пример 2:

Ввод: nums = [1,3,4,6,7], target = 5
Вывод: [-1,-1]

Пример 3:

Ввод: nums = [1,3,5], target = 5
Вывод: [2,2]

Ограничения:

len(nums) >= 1

public class Solution
{
    // Ответ будет находиться в элементе, указывающем на left
    // Поэтому сдвигаем right на 1 вправо, чтобы left мог принимать
    // значения [0, nums.Count - 1], то есть от первого и до последнего
    // индекса включительно
    public static int SearchLastTarget(List<int> nums, int target)
    {
        int left = 0, right = nums.Count;
        while (right - left > 1)
        {
            int mid = (left + right) / 2;
            if (nums[mid] <= target)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }

    // Ответ будет находиться в элементе, указывающем на right
    // Поэтому сдвигаем left на 1 влево, чтобы right мог принимать
    // значения [0, nums.Count - 1], то есть от первого и до последнего
    // индекса включительно
    public static int SearchFirstTarget(List<int> nums, int target)
    {
        int left = -1, right = nums.Count - 1;
        while (right - left > 1)
        {
            int mid = (left + right) / 2;
            if (nums[mid] < target)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }

    public static List<int> Search(List<int> nums, int target)
    {
        if (nums.Count == 0)
        {
            return new List<int> { -1, -1 };
        }
        int firstIndex = SearchFirstTarget(nums, target);
        int lastIndex = SearchLastTarget(nums, target);
        return new List<int> { firstIndex, lastIndex };
    }
}

#include <vector>
using namespace std;

int searchLastTarget(const vector<int>& nums, int target) {
    // ответ будет находиться в элементе, указывающем на l
    // поэтому сдвигаем r на 1 вправо, чтобы l мог принимать
    // значения [0, len(nums) - 1], то есть от первого и до последнего
    // индекса включительно
    int l = 0, r = nums.size();
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (nums[m] <= target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[l] == target ? l : -1;
}

int searchFirstTarget(const vector<int>& nums, int target) {
    // ответ будет находиться в элементе, указывающем на r
    // поэтому сдвигаем l на 1 влево, чтобы r мог принимать
    // значения [0, len(nums) - 1], то есть от первого и до последнего
    // индекса включительно
    int l = -1, r = nums.size() - 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (nums[m] < target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[r] == target ? r : -1;
}

vector<int> search(const vector<int>& nums, int target) {
    if (nums.empty()) {
        return {-1, -1};
    }
    int l = searchFirstTarget(nums, target);
    int r = searchLastTarget(nums, target);
    return {l, r};
}

package main

func searchLastTarget(nums []int, target int) int {
    // ответ будет находиться в элементе, указывающем на l
    // поэтому сдвигаем r на 1 вправо, чтобы l мог принимать
    // значения [0, len(nums) - 1], то есть от первого и до последнего
    // индекса включительно
    l, r := 0, len(nums)
    for r-l > 1 {
        m := (l + r) / 2
        if nums[m] <= target {
            l = m
        } else {
            r = m
        }
    }
    if nums[l] == target {
        return l
    }
    return -1
}

func searchFirstTarget(nums []int, target int) int {
    // ответ будет находиться в элементе, указывающем на r
    // поэтому сдвигаем l на 1 влево, чтобы r мог принимать
    // значения [0, len(nums) - 1], то есть от первого и до последнего
    // индекса включительно
    l, r := -1, len(nums)-1
    for r-l > 1 {
        m := (l + r) / 2
        if nums[m] < target {
            l = m
        } else {
            r = m
        }
    }
    if nums[r] == target {
        return r
    }
    return -1
}

func search(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }
    l := searchFirstTarget(nums, target)
    r := searchLastTarget(nums, target)
    return []int{l, r}
}

import java.util.List;

public class Solution {

    public int searchLastTarget(List<Integer> nums, int target) {
        // ответ будет находиться в элементе, указывающем на l
        // поэтому сдвигаем r на 1 вправо, чтобы l мог принимать
        // значения [0, nums.size() - 1], то есть от первого и до последнего
        // индекса включительно
        int l = 0, r = nums.size();
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (nums.get(m) <= target) {
                l = m;
            } else {
                r = m;
            }
        }
        return nums.get(l) == target ? l : -1;
    }

    public int searchFirstTarget(List<Integer> nums, int target) {
        // ответ будет находиться в элементе, указывающем на r
        // поэтому сдвигаем l на 1 влево, чтобы r мог принимать
        // значения [0, nums.size() - 1], то есть от первого и до последнего
        // индекса включительно
        int l = -1, r = nums.size() - 1;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (nums.get(m) < target) {
                l = m;
            } else {
                r = m;
            }
        }
        return nums.get(r) == target ? r : -1;
    }

    public List<Integer> search(List<Integer> nums, int target) {
        if (nums.size() == 0) {
            return List.of(-1, -1);
        }
        int l = searchFirstTarget(nums, target);
        int r = searchLastTarget(nums, target);
        return List.of(l, r);
    }
}

from typing import *

def search_last_target(nums: List[int], target: int) -> int:
    # ответ будет находится в элементе, указывающем на l
    # поэтому сдвигаем r на 1 вправо, чтобы l мог принимать
    # значения [0, len(nums) - 1], то есть от первого и до последнего
    # индекса включительно
    l, r = 0, len(nums)
    while r - l > 1:
        m = (l + r) // 2
        if nums[m] <= target:
            l = m
        else:
            r = m
    return l if nums[l] == target else -1

def search_first_target(nums: List[int], target: int) -> int:
    # ответ будет находится в элементе, указывающем на r
    # поэтому сдвигаем l на 1 влево, чтобы r мог принимать
    # значения [0, len(nums) - 1], то есть от первого и до последнего
    # индекса включительно
    l, r = -1, len(nums) - 1
    while r - l > 1:
        m = (l + r) // 2
        if nums[m] < target:
            l = m
        else:
            r = m
    return r if nums[r] == target else -1

def search(nums: List[int], target: int) -> List[int]:
    if len(nums) == 0:
        return [-1, -1]
    l = search_first_target(nums, target)
    r = search_last_target(nums, target)
    return [l, r]

function searchLastTarget(nums, target) {
    // ответ будет находится в элементе указывающим на l
    // поэтому сдвигаем r на 1 вправо, чтобы l мог принимать
    // значения [0, nums.length - 1], то есть от первого и до последнего
    // индекса включительно
    let l = 0;
    let r = nums.length;
    while (r - l > 1) {
        let m = Math.floor((l + r) / 2);
        if (nums[m] <= target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[l] === target ? l : -1;
}

function searchFirstTarget(nums, target) {
    // ответ будет находится в элементе указывающим на r
    // поэтому сдвигаем l на 1 влево, чтобы r мог принимать
    // значения [0, nums.length - 1], то есть от первого и до последнего
    // индекса включительно
    let l = -1;
    let r = nums.length - 1;
    while (r - l > 1) {
        let m = Math.floor((l + r) / 2);
        if (nums[m] < target) {
            l = m;
        } else {
            r = m;
        }
    }
    return nums[r] === target ? r : -1;
}

export function search(nums, target) {
    if (nums.length === 0) {
        return [-1, -1];
    }
    let l = searchFirstTarget(nums, target);
    let r = searchLastTarget(nums, target);
    return [l, r];
}

Оценка сложности

Время: O(log(n)), где n - длина массива nums
Память: O(1)