A problem reminding that O(2*Log(N)) is equal to O(Log(N))
Problem is by Leetcode: "Find First and Last Position of Element in Sorted Array", right here: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
Given an array of integers
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]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
The problem is looking for a Log(N) solution, but there are two values being asked for - the lower left, and the upper right. The way to find each one is to do a variation of binary search. And for each value, just run the algorithm twice for a O(2*Log(N)), which is the same as O(Log(N)). Code is below, cheers, Marcelo.
public class Solution
{
public int[] SearchRange(int[] nums, int target)
{
int[] retVal = new int[2];
if (nums == null || nums.Length == 0)
{
retVal[0] = -1;
retVal[1] = -1;
return retVal;
}
//Leftmost
int e1 = -1;
int left = 0;
int right = nums.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (nums[mid] == target && (mid == 0 || nums[mid - 1] < target))
{
e1 = mid;
break;
}
else if (nums[mid] >= target) right = mid - 1;
else left = mid + 1;
}
//Rightmost
int e2 = -1;
left = 0;
right = nums.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (nums[mid] == target && (mid == nums.Length - 1 || nums[mid + 1] > target))
{
e2 = mid;
break;
}
else if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
retVal[0] = e1;
retVal[1] = e2;
return retVal;
}
}
Ha, in C++ it's so easy to cheat :)
ReplyDeleteclass Solution {
public:
vector searchRange(vector& nums, int target) {
int startIdx = -1;
int endIdx = -1;
auto start = lower_bound(nums.cbegin(), nums.cend(), target);
if (start != nums.cend() && *start == target) {
startIdx = distance(nums.cbegin(), start);
}
auto end = upper_bound(nums.cbegin(), nums.cend(), target) - 1;
if (end != nums.cend() && *end == target) {
endIdx = distance(nums.cbegin(), end);
}
return {startIdx, endIdx};
}
};
a non-cheating answer in C++ is below:
Deleteclass Solution {
private:
int findFirst(const vector& nums, int target) const {
int left = 0;
int right = nums.size()-1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left < nums.size() && nums[left] == target ? left : -1;
}
int findLast(const vector& nums, int target) const {
int left = 0;
int right = nums.size()-1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right >= 0 && nums[right] == target ? right : -1;
}
public:
vector searchRange(vector& nums, int target) {
if (nums.empty()) return {-1, -1};
return {findFirst(nums, target), findLast(nums, target)};
}
};