Python&Java双语解决力扣必刷算法，题号34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给你一个按照非递减顺序排列的整数数组 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 <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
解题思路
要设计一个时间复杂度为 O(log n) 的算法来解决这个问题，我们可以使用二分查找法。由于数组是非递减顺序排列的，我们可以通过二分查找来定位目标值 target 的开始位置和结束位置。
具体步骤如下：
- 定义一个辅助函数
binarySearch，该函数接受数组nums、目标值target和一个布尔值leftBias作为参数。leftBias用于指示当找到target时是偏向左边还是右边。如果leftBias为true，则在找到target后继续向左查找，以确定target的最左边界；如果leftBias为false，则向右查找以确定target的最右边界。 - 使用
binarySearch函数两次，第一次传入leftBias为true以找到target的开始位置，第二次传入leftBias为false以找到target的结束位置。 - 如果在第一次查找中没有找到
target，则返回[-1, -1]。 - 如果找到了
target，则返回开始位置和结束位置。
完整代码
Java
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = binarySearch(nums, target, true);
if (start == nums.length || nums[start] != target) {
return new int[]{-1, -1};
}
int end = binarySearch(nums, target, false) - 1;
return new int[]{start, end};
}
// 二分查找辅助函数
private int binarySearch(int[] nums, int target, boolean leftBias) {
int low = 0, high = nums.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] > target || (leftBias && nums[mid] == target)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}
通过
Python
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binarySearch(leftBias: bool) -> int:
low, high = 0, len(nums) - 1
index = -1
while low <= high:
mid = (low + high) // 2
if target > nums[mid]:
low = mid + 1
elif target < nums[mid]:
high = mid - 1
else:
index = mid
if leftBias:
high = mid - 1 # 向左继续查找
else:
low = mid + 1 # 向右继续查找
return index
start = binarySearch(True)
if start == -1:
return [-1, -1] # 如果没有找到起始位置，说明数组中没有目标值，直接返回[-1, -1]
end = binarySearch(False)
return [start, end] 这个实现中，searchRange 方法包含了一个名为 binarySearch 的内部函数，该函数接受一个布尔参数 leftBias 来指示搜索方向。如果 leftBias 为 True，则搜索目标值的开始位置；如果为 False，则搜索结束位置。
-
当找到目标值时，如果
leftBias为True，则将high指针移动到mid - 1以继续在左侧搜索目标值的最左边界；反之，如果leftBias为False，则将low指针移动到mid + 1以在右侧继续搜索目标值的最右边界。 -
binarySearch函数返回目标值在数组中的索引（如果找到），或-1（如果未找到）。 -
最终，通过两次调用
binarySearch函数（一次寻找开始位置，一次寻找结束位置），并返回结果数组[start, end]。如果start为-1，表示目标值不在数组中，直接返回[-1, -1]。
通过
