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 length = nums?.Length ?? 0;
if (length == 0)
{
return new int[] {-1, -1 };
}
if (length == 1)
{
return nums[0] == target ? new int[] {0, 0} : new int[] {-1, -1};
}
int first = this.FindFirstOccurence(nums, target, 0, length - 1);
if (first == -1)
{
return new int[] {-1, -1 };
}
return new int[] {first, this.FindLastOccurence(nums, target, 0, length - 1) };
}
private int FindFirstOccurence(int[] nums, int target, int low, int high)
{
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;
if (nums[mid] == target && (mid == 0 || nums[mid] > nums[mid - 1]))
{
return mid;
}
if (target <= nums[mid])
{
return this.FindFirstOccurence(nums, target, low, mid - 1);
}
return this.FindFirstOccurence(nums, target, mid + 1, high);
}
private int FindLastOccurence(int[] nums, int target, int low, int high)
{
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;
if (nums[mid] == target && (mid == nums.Length - 1 || nums[mid] < nums[mid + 1]))
{
return mid;
}
if (target < nums[mid])
{
return this.FindLastOccurence(nums, target, low, mid - 1);
}
return this.FindLastOccurence(nums, target, mid + 1, high);
}
Complexity: O(log n)
No comments:
Post a Comment