https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
- code
class Solution {
public int[] searchRange(int[] nums, int target) {
// find left
int start = 0;
int end = nums.length;
while (start < end){
int mid = start + (end - start) / 2;
if (nums[mid] < target){
start = mid + 1;
}else{
end = mid;
}
}
// find right position
int l = 0;
int r = nums.length - 1;
while (l <= r){
int m = l + (r - l) / 2;
if (nums[m] > target){
r = m - 1;
}else{
l = m + 1;
}
}
if (start > r){
start = -1;
r = -1;
}
return new int[]{start, r};
}
}
- code
class Solution:
def searchRange(self, nums, target):
def binarySearchLeft(A, x):
left, right = 0, len(A) - 1
while left <= right:
mid = (left + right) // 2
if x > A[mid]: left = mid + 1
else: right = mid - 1
return left
def binarySearchRight(A, x):
left, right = 0, len(A) - 1
while left <= right:
mid = (left + right) // 2
if x >= A[mid]: left = mid + 1
else: right = mid - 1
return right
left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
return (left, right) if left <= right else [-1, -1]
- code
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left_point = bisect.bisect_left(nums, target)
if not nums or left_point == len(nums):
return [-1,-1]
if nums[left_point] == target:
right_point = left_point
while right_point+1 < len(nums) and nums[right_point+1] == target:
right_point += 1
return [left_point, right_point]
else:
return [-1,-1]