AlgoPressAppearance
0034-在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
给定一个按照升序排列的整数数组 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 <= 10^5
- -10^9<= nums[i]<= 10^9
- nums是一个非递减数组
- -10^9<= target<= 10^9
思路：二分查找
注意下面的方法，当找到 target 值的时候，会出现线性扫描，所以算法复杂度会是 O(n)
csharp
public class Solution {
public int[] SearchRange(int[] nums, int target) {
int[] result = new int[]{-1,-1};
int left = 0;
int right = nums.Length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
//查找左边界
for(int i=mid; i>=0; i--){
if(nums[i] == target){
result[0] = i;
}
else{
break;
}
}
//查找右边界
for(int i=mid; i<nums.Length;i++){
if(nums[i] == target){
result[1] = i;
}
else{
break;
}
}
break;
}
else if(target > nums[mid]){
left = mid+1;
}
else{
right = mid-1;
}
}
return result;
}
}
思路：二分查找 优化
csharp
public class Solution {
private int LeftBound(int[] nums, int target){
int left = 0;
int right = nums.Length-1;
while(left <= right){
int mid = left + (right - left) / 2;
if(target > nums[mid]){
left = mid + 1;
}
else {
right = mid - 1;
}
}
if(left >= nums.Length || nums[left] != target){
return -1;
}
return left;
}
private int RightBound(int[] nums, int target){
int left = 0;
int right = nums.Length-1;
while(left <= right){
int mid = left + (right - left) / 2;
if(target >= nums[mid]){
left = mid + 1;
}
else{
right = mid - 1;
}
}
if(right < 0 || nums[right] != target){
return -1;
}
return right;
}
public int[] SearchRange(int[] nums, int target) {
int[] result = new int[]{-1,-1};
int leftBound = LeftBound(nums,target);
if(leftBound != -1){
int rightBound = RightBound(nums,target);
result[0] = leftBound;
result[1] = rightBound;
}
return result;
}
}