solution/0000-0099/0034.Find First and Last Position of Element in Sorted Array/README.md · jiajin2coding/leetcode

# [34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array)

[English Version](/solution/0000-0099/0034.Find%20First%20and%20Last%20Position%20of%20Element%20in%20Sorted%20Array/README_EN.md)

## 题目描述

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

如果数组中不存在目标值 <code>target</code>，返回&nbsp;<code>[-1, -1]</code>。

你必须设计并实现时间复杂度为&nbsp;<code>O(log n)</code>&nbsp;的算法解决此问题。

&nbsp;

示例 1：

<pre>
输入：nums = [<code>5,7,7,8,8,10]</code>, target = 8
输出：[3,4]</pre>

示例&nbsp;2：

<pre>
输入：nums = [<code>5,7,7,8,8,10]</code>, target = 6
输出：[-1,-1]</pre>

示例 3：

<pre>
输入：nums = [], target = 0
输出：[-1,-1]</pre>

&nbsp;

提示：

<ul>
	<li><code>0 &lt;= nums.length &lt;= 105</code></li>
	<li><code>-109&nbsp;&lt;= nums[i]&nbsp;&lt;= 109</code></li>
	<li><code>nums</code>&nbsp;是一个非递减数组</li>
	<li><code>-109&nbsp;&lt;= target&nbsp;&lt;= 109</code></li>
</ul>

## 解法

**方法一：二分查找**

两遍二分，分别查找出左边界和右边界。

以下是二分查找的两个通用模板：

模板 1：

```java
boolean check(int x) {}

int search(int left, int right) {
 while (left < right) {
 int mid = (left + right) >> 1;
 if (check(mid)) {
 right = mid;
 } else {
 left = mid + 1;
 }
 }
 return left;
}
```

模板 2：

```java
boolean check(int x) {}

int search(int left, int right) {
 while (left < right) {
 int mid = (left + right + 1) >> 1;
 if (check(mid)) {
 left = mid;
 } else {
 right = mid - 1;
 }
 }
 return left;
}
```

做二分题目时，可以按照以下步骤：

1. 写出循环条件：`while (left < right)`，注意是 `left < right`，而非 `left <= right`；
1. 循环体内，先无脑写出 `mid = (left + right) >> 1`；
1. 根据具体题目，实现 `check()` 函数（有时很简单的逻辑，可以不定义 `check`），想一下究竟要用 `right = mid`（模板 1） 还是 `left = mid`（模板 2）；
 - 如果 `right = mid`，那么无脑写出 else 语句 `left = mid + 1`，并且不需要更改 mid 的计算，即保持 `mid = (left + right) >> 1`；
 - 如果 `left = mid`，那么无脑写出 else 语句 `right = mid - 1`，并且在 mid 计算时补充 +1，即 `mid = (left + right + 1) >> 1`。
1. 循环结束时，left 与 right 相等。

注意，这两个模板的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处的位置。 对于可能无解的情况，只要判断二分结束后的 left 或者 right 是否满足题意即可。

### **Python3**

```python
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l = bisect_left(nums, target)
        r = bisect_left(nums, target + 1)
        return [-1, -1] if l == len(nums) or l >= r else [l, r - 1]
```

### **Java**

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = search(nums, target);
        int r = search(nums, target + 1);
        return l == nums.length || l >= r ? new int[]{-1, -1} : new int[]{l, r - 1};
    }

private int search(int[] nums, int target) {
 int left = 0, right = nums.length;
 while (left < right) {
 int mid = (left + right) >>> 1;
 if (nums[mid] >= target) {
 right = mid;
 } else {
 left = mid + 1;
 }
 }
 return left;
 }
}
```

### **C++**

```cpp
class Solution {
public:
 vector<int> searchRange(vector<int>& nums, int target) {
 int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
 int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin();
 if (l == nums.size() || l >= r) return {-1, -1};
 return {l, r - 1};
 }
};
```

### **JavaScript**

```js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
 function search(target) {
 let left = 0,
 right = nums.length;
 while (left < right) {
 const mid = (left + right) >> 1;
 if (nums[mid] >= target) {
 right = mid;
 } else {
 left = mid + 1;
 }
 }
 return left;
 }
 const l = search(target);
 const r = search(target + 1);
 return l == nums.length || l >= r ? [-1, -1] : [l, r - 1];
};
```

### **Go**

```go
func searchRange(nums []int, target int) []int {
	search := func(target int) int {
		left, right := 0, len(nums)
		for left < right {
			mid := (left + right) >> 1
			if nums[mid] >= target {
				right = mid
			} else {
				left = mid + 1
			}
		}
		return left
	}
	l, r := search(target), search(target+1)
	if l == len(nums) || l >= r {
		return []int{-1, -1}
	}
	return []int{l, r - 1}
}
```

### **Rust**

```rust
impl Solution {
 pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
 let n = nums.len();
 let search = |target| {
 let mut left = 0;
 let mut right = n;
 while left < right {
 let mid = left + (right - left) / 2;
 if nums[mid] < target {
 left = mid + 1;
 } else {
 right = mid;
 }
 }
 left
 };
 let start = search(target);
 let end = search(target + 1) - 1;
 if start >= n || nums[start] != target {
 return vec![-1, -1];
 }
 vec![start as i32, end as i32]
 }
}
```

### **TypeScript**

```ts
function searchRange(nums: number[], target: number): number[] {
 function search(target) {
 let left = 0,
 right = nums.length;
 while (left < right) {
 const mid = (left + right) >> 1;
 if (nums[mid] >= target) {
 right = mid;
 } else {
 left = mid + 1;
 }
 }
 return left;
 }
 const l = search(target);
 const r = search(target + 1);
 return l == nums.length || l >= r ? [-1, -1] : [l, r - 1];
}
```

```ts
function searchRange(nums: number[], target: number): number[] {
 const n = nums.length;
 const search = (target: number) => {
 let left = 0;
 let right = n;
 while (left < right) {
 const mid = (left + right) >>> 1;
 if (nums[mid] < target) {
 left = mid + 1;
 } else {
 right = mid;
 }
 }
 return left;
 };
 const start = search(target);
 const end = search(target + 1) - 1;
 if (nums[start] !== target) {
 return [-1, -1];
 }
 return [start, end];
}
```

### **...**

```

jiajin2coding/leetcode

About

Releases

Contributors

Language(Optional)

Activities