Problem: 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:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Approach: We can use binary search to find the first position and last position of the target given the array is sorted.
Implementation in C#:
public int[] SearchRange(int[] nums, int target)
{
int first = this.FindFirstOccrence(nums, target);
if (first == -1)
{
return new int[] {first, first};
}
return new int[] {first,
this.FindLastOccrence(nums, target)};
}
private int FindFirstOccrence(int[] nums, int target)
{
int start = 0, end = nums.Length - 1;
while (start <= end)
{
int mid = start + (end - start) / 2;
if (nums[mid] == target &&
(mid == 0 || nums[mid] > nums[mid - 1]))
{
return mid;
}
else if (nums[mid] < target)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return -1;
}
private int FindLastOccrence(int[] nums, int target)
{
int start = 0, end = nums.Length - 1;
while (start <= end)
{
int mid = start + (end - start) / 2;
if (nums[mid] == target &&
(mid == nums.Length - 1
|| nums[mid] < nums[mid + 1]))
{
return mid;
}
else if (nums[mid] <= target)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
return -1;
}
Complexity: O(log n)
No comments:
Post a Comment