# 题目

• 示例 1：
输入：nums = [5,7,7,8,8,10], target = 8


• 示例 2：
输入：nums = [5,7,7,8,8,10], target = 6


• 示例 3：
输入：nums = [], target = 0



0 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

nums 是一个非递减数组

-10^9 <= target <= 10^9

# 解题思路

## java 实现

public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
int index = binarySearch(nums, target);
if(-1 == index) {
return result;
}
for(int i = index; i >= 0; i--) {
if(nums[i] != target) {
break;
} else {
// 如果相同
result[0] = i;
}
}
// 设置最后一个
for(int i = index; i < nums.length; i++) {
if(nums[i] != target) {
break;
} else {
result[1] = i;
}
}
return result;
}

/**
* 二分法找到的元素可能不是刚好的。
* @param nums
* @param target
* @return
*/
private static int binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high)/2;
if(target == nums[mid]) {
return mid;
} else if(target < nums[mid]) {
// 偏大
high = mid-1;
} else {
low = mid + 1;
}
}
return -1;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 42 MB, less than 88.37% of Java online submissions for Find First and Last Position of Element in Sorted Array.


# 继续优化

## java 实现

public int[] searchRange(int[] nums, int target) {
// 参数校验
if(nums == null) {
// 或者抛出异常
return null;
}
int first = binarySearchFirst(nums, target);
int last = binarySearchLast(nums, target);
return new int[]{first, last};
}

/**
* 二分法找到的元素第一次出现的位置
* @param nums 数组
* @param target 目标值
* @return 结果下标
*/
private static int binarySearchFirst(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high)/2;
if(target == nums[mid]) {
// 调整一下返回的条件
// 如果是第一个元素，获取上一个元素不等于当前元素
if(mid == 0 || (nums[mid-1] != target)) {
return mid;
} else {
// 否则的话，high 调整为 mid 的上一个位置
high = mid-1;
}
} else if(target < nums[mid]) {
// 偏大
high = mid-1;
} else {
low = mid + 1;
}
}
return -1;
}

/**
* 二分法找到的元素最后一次出现的位置
* @param nums 数组
* @param target 目标值
* @return 结果下标
*/
private static int binarySearchLast(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high)/2;
if(target == nums[mid]) {
// 调整一下返回的条件
// 如果是第一个元素，获取上一个元素不等于当前元素
if(mid == nums.length-1 || (nums[mid+1] != target)) {
return mid;
} else {
// 否则的话，low 调整为 mid 的下一个位置
low = mid+1;
}
} else if(target < nums[mid]) {
// 偏大
high = mid-1;
} else {
low = mid + 1;
}
}
return -1;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 42.6 MB, less than 23.21% of Java online submissions for Find First and Last Position of Element in Sorted Array.


# 这是优化的尽头吗？

## 更进一步的优化

1 2 3 3 3 3 4 5


（1）第一次出现，找到下标为 2 的 元素3。

（2）最后一次出现，找到下标为 5 的元素3。

## java 实现

public int[] searchRange(int[] nums, int target) {
// 参数校验
if(nums == null) {
// 或者抛出异常
return null;
}
int first = binarySearchFirst(nums, target);
int last = binarySearchLast(nums, target, first);
return new int[]{first, last};
}

/**
* 二分法找到的元素第一次出现的位置
* @param nums 数组
* @param target 目标值
* @return 结果下标
*/
private static int binarySearchFirst(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high)/2;
if(target == nums[mid]) {
// 调整一下返回的条件
// 如果是第一个元素，获取上一个元素不等于当前元素
if(mid == 0 || (nums[mid-1] != target)) {
return mid;
} else {
// 否则的话，high 调整为 mid 的上一个位置
high = mid-1;
}
} else if(target < nums[mid]) {
// 偏大
high = mid-1;
} else {
low = mid + 1;
}
}
return -1;
}

/**
* 二分法找到的元素最后一次出现的位置
* @param nums 数组
* @param target 目标值
* @param low 开始位置
* @return 结果下标
*/
private static int binarySearchLast(int[] nums, int target, int low) {
// 快速失败
if(low == -1) {
return -1;
}
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high)/2;
if(target == nums[mid]) {
// 调整一下返回的条件
// 如果是第一个元素，获取上一个元素不等于当前元素
if(mid == nums.length-1 || (nums[mid+1] != target)) {
return mid;
} else {
// 否则的话，low 调整为 mid 的下一个位置
low = mid+1;
}
} else if(target < nums[mid]) {
// 偏大
high = mid-1;
} else {
low = mid + 1;
}
}
return -1;
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 42.5 MB, less than 23.21% of Java online submissions for Find First and Last Position of Element in Sorted Array.


# 参考资料

• 顺序查找

https://www.cnblogs.com/yw09041432/p/5908444.html

https://www.jb51.net/article/53863.htm

https://blog.csdn.net/jiandanokok/article/details/50517837

• 二分查找

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html