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]
Solution
This challenge is a fairly straightforward one when you try to solve with for loop; however, the question explicitly mentioned that runtime should be O(log n) which is why to find an efficient solution, you must know how to implement a Binary Search Algorithm.
The most important thing to note here is that, you can only use BSA (Binary Search Algorithm) when an array is sorted.
Code for a basic implementation of Binary search algorithm - BSA
Pseudocode for binary search alorithm:
1. Get first and last position of an array. Set Left L- to 0 and Right R- to N-1, to get first and last position of an array.
2. while L <= R
3. set Middle M - (L+R)/2 , to find the middle value of a sorted array.
4. if M < T (Target) then set L = m+1, then go to STEP 2
5. if M > T (Target) then set R = m-1, then go to STEP 2
6. if M== T , then search is complete, return M.
Now, the above BS algorithm can be applied on the current problem to achieve O(log n) runtime.
For example:
A sorted array = [5,7,7,8,8,10] with T = 8. To first the answer which is [3,4], you can do use one of the two approaches.
Approach #1:
The way I have tried to solve this problem is that first of all, you could find a middle value using BSA, and after that I have tried to go through loop on forward and backward direction to find the first and last element. If forward or backward element doesn't exist, then return the same value.
Pseudocode
1. After finding M, using BSA,
2. check if M of an array + 1 (forward position), is similar to the target value - array[middle+1]
Loop through element until the last element that is equal to T
Save the last position as LastIndex
3. Check if M of an array - 1 (backward position), is similar to the target value - array[middle-1]
Follow same sub tasks of No. 2, but with reverse loop to find the first element that is equal to T
Save the first position as FirstIndex
4. If cannot find M = T, then return {-1,-1}
4. Return {FirstIndex, LastIndex}
Implementation
vector<int> searchRange(vector<int> &numbs, int target)
{
vector<int> v;
int start = 0;
int end = numbs.size() - 1;
int middle = -1;
int value = -1;
int f = -1;
int l = -1;
while (start <= end)
{
middle = (start + end) / 2;
if (target < numbs[middle])
{
end = middle - 1;
}
else if (target > numbs[middle])
{
start = middle + 1;
}
else
{
value = middle;
break;
}
}
if (value == -1)
{
v.push_back(f);
v.push_back(l);
return v;
}
if (numbs[middle + 1] == target)
{
for (int i = middle; i <= end; i++)
{
if (numbs[i] == target)
{
l = i;
}
else
{
break;
}
}
}
else
{
l = middle;
}
if (numbs[middle - 1] == target)
{
for (int i = middle; i >= 0; i--)
{
if (numbs[i] == target)
{
f = i;
}
else
{
break;
}
}
}
else
{
f = middle;
}
// v.push_back(binary_search(numbs, target, true));
// v.push_back(binary_search(numbs, target, false));
return {f, l};
}
Approach #2:
Second approach is similar but instead of using for loops, you can utilize Binary Search algorithm to find first index of a particular element and then the same way run through Binary Search algorithm again to find last index of a particular element. Below explanation will make it clear..
Pseudocode
1. Basic BSA (Check pseudocode for BSA written above) implementation, but when M=T, follow step 2.
2. Define boolean switch to find FIRST and LAST index, isFirst = true/false.
3. if isFirst = true
then R = middle - 1; //To check till the last element on left side of an array.
if isFirst = false
then L = middle + 1; //To check till the first element on left side of an array.
Please check below implementation and code comments to understand it better.
int binary_search(vector<int> &nums, int target, bool isLeft)
{
printVect(nums);
int start = 0;
int end = nums.size() - 1;
int middle;
// [5,7,7,8,8,8]
// middle = 7 , start = 5, end = 8, target = 8
int value = -1;
while (start <= end)
{
middle = (start + end) / 2; // 0+5/2 = 2 --- middle = 7 || 2. (3+5)/2 = 8/2=4 m = 4(8) || 3.
if (target < nums[middle])
{ // 1 = 8 < 7
end = middle - 1; // 1 = start = 2+1 = 3,
}
else if (target > nums[middle])
{
start = middle + 1;
}
else
{
value = middle;
if (isLeft)
{ // if want to go left, then minimize right, if want to go right, then minimize left size.
end = middle - 1;
// to check the first element where there will be no middle, far left 3+5/2= 8/2 = 4
}
else
{
start = middle + 1;
// to check the last element where there will be no middle, far right 5+5/2 = 5 = same position so it means we reached the end
}
}
}
return value;
}Thanks for checking out and if you have a suggestion or question, please comment below. Happy coding.
0 Comments