leetcode 34 丢失的数字(find-first-and-last-position-of-element-in-sorted-array)

0034 find-first-and-last-position-of-element-in-sorted-array

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

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

Follow up: Could you 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

题目大意

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。

解题思路 1

给出一个有序数组nums和一个数target，要求在数组中找到第一个和这个元素相等的元素下标，最后一个和这个元素相等的元素下标。

这一题是经典的二分搜索变种题。二分搜索有4大基础变种题：

1. 查找第一个值等于给定值的元素
2. 查找最后一个值等于给定值的元素
3. 查找第一个大于等于给定值的元素
4. 查找最后一个大于等于给定值的元素

这一题的解题思路可以分别利用变种 1 和变种 2 的解法就可以做出此题。(4 大基础变种的实现见代码)

1.查找第一个值等于给定值的元素

首先让我们找到范围的左边界。我们将范围初始化为[left = 0，right = n-1]。在每个步骤中，计算中间元素[mid =（i + j）/ 2]。现在根据目标nums[mid]的相对值，存在三种可能性：

1. 如果nums[mid] < target，right = mid-1进入下一次迭代
2. 如果nums[mid]> target，left = mid+1进入下一次迭代
3. 如果nums[mid] = target，又有两种情况
   1. mid == 0 或者中值的前一个元素nums[mid-1] != target，则mid就是我们要找的第一个值
   2. 否则mid还不是我们要找的第一个值，前面还有相等的值，则right = mid-1进入下一次迭代

2.查找最后一个值等于给定值的元素

首先让我们找到范围的右边界。我们将范围初始化为[left = 0，right = n-1]。在每个步骤中，计算中间元素[mid =（i + j）/ 2 +1]（这里+1使得中值偏向右边）。现在根据目标nums[mid]的相对值，存在三种可能性：

1. 如果nums[mid] < target，right = mid-1进入下一次迭代
2. 如果nums[mid]> target，left = mid+1进入下一次迭代
3. 如果nums[mid] = target，又有两种情况
   1. mid == len(nums) - 1 或者中值的前一个元素nums[mid+1] != target，则mid就是我们要找的最后一个值
   2. 否则mid还不是我们要找的最后一个值，后面还有相等的值，则left = mid+1进入下一次迭代

3.查找第一个大于等于给定值的元素

首先让我们找到范围的左边界。我们将范围初始化为[left = 0，right = n-1]。在每个步骤中，计算中间元素[mid =（i + j）/ 2]。现在根据目标nums[mid]的相对值，存在三种可能性：

1. 如果nums[mid] < target，left = mid+1进入下一次迭代
2. 如果nums[mid] >= target，又有两种情况
   1. mid == 0 或者中值的前一个元素nums[mid-1] < target，则mid就是我们要找的第一个值
   2. 否则mid还不是我们要找的第一个值，前面还有相等的值，则right = mid-1进入下一次迭代

4.查找最后一个大于等于给定值的元素

首先让我们找到范围的右边界。我们将范围初始化为[left = 0，right = n-1]。在每个步骤中，计算中间元素[mid =（i + j）/ 2 +1]（这里+1使得中值偏向右边）。现在根据目标nums[mid]的相对值，存在三种可能性：

1. 如果nums[mid] > target，right = mid-1进入下一次迭代
2. 如果nums[mid] <= target，又有两种情况
   1. mid == len(nums) - 1 或者中值的前一个元素nums[mid+1] > target，则mid就是我们要找的最后一个值
   2. 否则mid还不是我们要找的最后一个值，后面还有大于相等的值，则left = mid+1进入下一次迭代

Go

Rust