同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
Given an array of integers nums
sorted in non-decreasing order, find the starting and ending position of a given target
value.
If target
is not found in the array, return [-1, -1]
.
You must write an algorithm with O(log n)
runtime complexity.
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]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
We can perform binary search twice to find the left and right boundaries respectively.
The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.
Below are two general templates for binary search:
Template 1:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
Template 2:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
When doing binary search problems, you can follow the following routine:
Note that the advantage of these two templates is that they always keep the answer within the binary search interval, and the value corresponding to the end condition of the binary search is exactly at the position of the answer. For the case that may have no solution, just check whether the $left$ or $right$ after the binary search ends satisfies the problem.
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l = bisect_left(nums, target)
r = bisect_left(nums, target + 1)
return [-1, -1] if l == r else [l, r - 1]
class Solution {
public int[] searchRange(int[] nums, int target) {
int l = search(nums, target);
int r = search(nums, target + 1);
return l == r ? new int[] {-1, -1} : new int[] {l, r - 1};
}
private int search(int[] nums, int x) {
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin();
if (l == r) return {-1, -1};
return {l, r - 1};
}
};
func searchRange(nums []int, target int) []int {
l := sort.SearchInts(nums, target)
r := sort.SearchInts(nums, target+1)
if l == r {
return []int{-1, -1}
}
return []int{l, r - 1}
}
function searchRange(nums: number[], target: number): number[] {
const search = (x: number): number => {
let [left, right] = [0, nums.length];
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
};
const l = search(target);
const r = search(target + 1);
return l === r ? [-1, -1] : [l, r - 1];
}
impl Solution {
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
let n = nums.len();
let search = |x| {
let mut left = 0;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] < x {
left = mid + 1;
} else {
right = mid;
}
}
left
};
let l = search(target);
let r = search(target + 1);
if l == r {
return vec![-1, -1];
}
vec![l as i32, (r - 1) as i32]
}
}
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
function search(x) {
let left = 0,
right = nums.length;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
const l = search(target);
const r = search(target + 1);
return l == r ? [-1, -1] : [l, r - 1];
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。