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

@TOC

## # 题目描述

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

Your algorithm's runtime complexity must be in the order of O(log n).

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

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]
``````

## # 解题方法

### # 二分查找

lower_bound返回的是开始的第一个满足条件的位置，而upper_bound返回的是第一个不满足条件的位置。所以，当两个相等的时候代表没有找到，如果找到了的话，需要返回的是[left, right - 1].

``````class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = self.lowwer_bound(nums, target)
right = self.higher_bound(nums, target)
if left == right:
return [-1, -1]
return [left, right - 1]

def lowwer_bound(self, nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) / 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left

def higher_bound(self, nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) / 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return left
``````

``````class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = bisect.bisect_left(nums, target)
right = bisect.bisect_right(nums, target)
if left == right:
return [-1, -1]
return [left, right - 1]
``````

C++代码自己手写lower_bound和upper_bound函数如下：

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int low = lower_bound(nums, target);
int high = upper_bound(nums, target);
if (low == high)
return {-1, -1};
else
return {low, high - 1};
}
int lower_bound(vector<int>& nums, int target) {
const int N = nums.size();
// [l, r)
int l = 0, r = N;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] >= target) {
r = mid;
} else  {
l = mid + 1;
}
}
return l;
}
int upper_bound(vector<int>& nums, int target) {
const int N = nums.size();
// [l, r)
int l = 0, r = N;
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] <= target) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
};
``````

C++代码使用lower_bound()和upper_bound()函数的代码如下：

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
auto low = lower_bound(nums.begin(), nums.end(), target);
auto high = upper_bound(nums.begin(), nums.end(), target);
if (low == high) return {-1, -1};
return {low - nums.begin(), high - nums.begin() - 1};
}
};
``````

## # 日期

2018 年 10 月 21 日 —— 新的一周又开始了 2019 年 1 月 11 日 —— 小光棍节？