java
[在排序数组中查找元素的第一个和最后一个位置
在这里如果只有一个目标元素，则返回的应该是相同的位置数值
线性扫描：
java:
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};
//数组类型 int[],数组值{-1，-1}
// find the index of the leftmost appearance of target.
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
targetRange[0] = i;
break;
}
}
// if the last loop did not find any index, then there is no valid range
// and we return [-1, -1].
if (targetRange[0] == -1) {
return targetRange;
}
// find the index of the rightmost appearance of target (by reverse
// iteration). it is guaranteed to appear.
for (int j = nums.length-1; j >= 0; j--) {
if (nums[j] == target) {
targetRange[1] = j;
break;
}
}
return targetRange;
}
}
二分查找python版本
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums: return [-1, -1]
# 确定左边界
left, right = 0, len(nums)-1
while left + 1 < right:
mid = (left + right) >> 1
if nums[mid] >= target:
//都是和mid进行比较的
//变化的是left和right，每次都是将mid赋给left或者right
right = mid
else:
left = mid
if nums[left] == target: lbound = left
elif nums[right] == target: lbound = right
else: return [-1, -1]
# 确定右边界
left, right = 0, len(nums)-1
while left + 1 < right:
mid = (left + right) >> 1
if nums[mid] <= target:
left = mid
else:
right = mid
if nums[right] == target: rbound = right
elif nums[left] == target: rbound = left
else: return [-1,-1]
return [lbound, rbound]
