Medium
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
To solve the “Find First and Last Position of Element in Sorted Array” problem in Swift with a Solution
class, we can follow these steps:
Solution
class.searchRange
that takes an integer array nums
and an integer target
as input and returns an integer array representing the starting and ending positions of target
in nums
. If target
is not found, return [-1, -1]
.target
.left
to 0 and the right pointer right
to the length of nums
minus 1.firstOccurrence
and lastOccurrence
to -1.target
:
left
is less than or equal to right
:
mid
as (left + right) / 2
.nums[mid]
is equal to target
, update firstOccurrence = mid
and continue searching on the left half by updating right = mid - 1
.target
is less than nums[mid]
, update right = mid - 1
.left = mid + 1
.target
:
left
to 0 and right
to the length of nums
minus 1.left
is less than or equal to right
:
mid
as (left + right) / 2
.nums[mid]
is equal to target
, update lastOccurrence = mid
and continue searching on the right half by updating left = mid + 1
.target
is greater than nums[mid]
, update left = mid + 1
.right = mid - 1
.[firstOccurrence, lastOccurrence]
.Here’s the implementation:
public class Solution {
public func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
var ans = [helper(nums, target, false), helper(nums, target, true)]
return ans
}
private func helper(_ nums: [Int], _ target: Int, _ equals: Bool) -> Int {
var l = 0
var r = nums.count - 1
var result = -1
while l <= r {
let mid = l + (r - l) / 2
if nums[mid] == target {
result = mid
}
if nums[mid] < target || (nums[mid] == target && equals) {
l = mid + 1
} else {
r = mid - 1
}
}
return result
}
}
This implementation provides a solution to the “Find First and Last Position of Element in Sorted Array” problem in Swift. It returns the starting and ending positions of target
in nums
using binary search, with a time complexity of O(log n).