Skip to content

Latest commit

 

History

History
146 lines (101 loc) · 4.28 KB

find-first-and-last-position-of-element-in-sorted-array.md

File metadata and controls

146 lines (101 loc) · 4.28 KB
Raw

34. Find First and Last Position of Element in Sorted Array - 在排序数组中查找元素的第一个和最后一个位置

Tags - 题目标签

Description - 题目描述

EN:

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109

ZH-CN:

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 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]

 

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language Runtime Memory Submission Time
typescript 64 ms 42.9 MB 2022/05/06 20:48 
function searchRange(nums: number[], target: number): number[] {
  return [searchFirst(nums, target), searchLast(nums, target)];
};


function searchFirst(nums: number[], target: number): number {
  if (nums.length === 0) {
    return -1;
  }
  if (nums.length === 1) {
    return nums[0] === target ? 0 : -1;
  }

  let i = 0, j = nums.length - 1, mid = Math.floor((i + j) / 2);

  while (i <= j) {
    mid = Math.floor((i + j) / 2);
    if (nums[mid] >= target) {
      j = mid - 1;
    } else {
      i = mid + 1;
    }
  }

  return (i >= nums.length || nums[i] !== target) ? -1 : i;
}

function searchLast(nums: number[], target: number): number {
  if (nums.length === 0) {
    return -1;
  }
  if (nums.length === 1) {
    return nums[0] === target ? 0 : -1;
  }

  let i = 0, j = nums.length - 1, mid = Math.floor((i + j) / 2);

  while (i <= j) {
    mid = Math.floor((i + j) / 2);
    if (nums[mid] > target) {
      j = mid - 1;
    } else {
      i = mid + 1;
    }
  }

  return (j < 0 || nums[j] !== target) ? -1 : j;
}

My Notes - 我的笔记

参考：【LeetCode】一个模板通杀所有「二分查找」问题