Table of Contents
Problem Description:
Given a sorted array of integers nums and a target element target, you need to find the starting and ending position of target in the array. If the target element is not present in the array, return [-1, -1].
You must perform this search in O(log n) time complexity.
Sample Input and Expected Output:
Input:
nums = [5, 7, 7, 8, 8, 10]
target = 8
Output:
Starting position of target 8: 3
Ending position of target 8: 4
Input:
nums = [5, 7, 7, 8, 8, 10]
target = 6
Output:
Target element 6 not found in the sorted array.
Solution in C++:
We can solve this problem using two binary searches: one to find the starting position and another to find the ending position of the target element. The binary search algorithm is modified to find the leftmost occurrence and rightmost occurrence of the target element.
#include <iostream>
#include <vector>
std::vector<int> searchRange(std::vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
std::vector<int> result{-1, -1};
// Find the starting position of target
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (left < nums.size() && nums[left] == target) {
result[0] = left;
} else {
// If the target is not found, return [-1, -1]
return result;
}
// Find the ending position of target
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
result[1] = right;
return result;
}
int main() {
std::vector<int> nums = {5, 7, 7, 8, 8, 10};
int target1 = 8;
int target2 = 6;
std::vector<int> result1 = searchRange(nums, target1);
std::vector<int> result2 = searchRange(nums, target2);
if (result1[0] != -1) {
std::cout << "Starting position of target " << target1 << ": " << result1[0] << std::endl;
std::cout << "Ending position of target " << target1 << ": " << result1[1] << std::endl;
} else {
std::cout << "Target element " << target1 << " not found in the sorted array." << std::endl;
}
if (result2[0] != -1) {
std::cout << "Starting position of target " << target2 << ": " << result2[0] << std::endl;
std::cout << "Ending position of target " << target2 << ": " << result2[1] << std::endl;
} else {
std::cout << "Target element " << target2 << " not found in the sorted array." << std::endl;
}
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(log n), where n is the size of the nums array. This is because we are performing two binary searches, each taking logarithmic time.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The output vector, result, is not considered in the space complexity analysis since it is part of the function’s return value.