34. Find First and Last Position of Element in Sorted Array
給定一個按非遞減順序排序的整數數組 nums，找到給定目標值的起始和結束位置。
如果在數組中找不到目標值，則返回 [-1, -1]。
你必須設計一個時間複雜度為 O(log n) 的算法。
範例 1：
輸入：nums = [5,7,7,8,8,10], target = 8 輸出：[3,4]
Python
from typing import List
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def findFirst(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
def findLast(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right
first = findFirst(nums, target)
last = findLast(nums, target)
if first <= last and first < len(nums) and nums[first] == target:
return [first, last]
else:
return [-1, -1]
17.81MB, 74ms
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int first = findFirst(nums, target);
int last = findLast(nums, target);
if (first <= last && first < nums.size() && nums[first] == target) {
return {first, last};
} else {
return {-1, -1};
}
}
private:
int findFirst(const vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int findLast(const vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
};
16.12MB, 0ms
Javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
function findFirst(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
function findLast(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
const first = findFirst(nums, target);
const last = findLast(nums, target);
if (first <= last && first < nums.length && nums[first] === target) {
return [first, last];
} else {
return [-1, -1];
}
};
49.58MB, 60ms
