find upper and lower bound
I did not get this question , Can you please help me how can i solve this question?
The question is simple. For a given sorted array of n elements, you have to find the lower and upper bound positions of T test case elements.If the element is not present in the array, you have to print -1.
This is an application of Binary search as you have learnt in the video lectures of the course.
Consider the sample case:
5 <=== n, number of elements in the array
1 2 3 3 4 <==== the array
3 <====no of test cases/search elements
2
3
10
Expected Output:
1 1 ===> since 2 is present at index 1. its lower and upper bound both is 1.
2 3 ===>since 3 is present at index 2 and 3. So its lower bound is 2 and upper bound is 3.
-1 -1===> since 10 is not present, so lower and upper bound is -1.
The overall algorithm works fairly similarly to the linear scan approach, except for the subroutine used to find the left and rightmost indices themselves. Here, we use a modified binary search to search a sorted array, with a few minor adjustments. First, because we are locating the leftmost (or rightmost) index containing target (rather than returning true iff we find target), the algorithm does not terminate as soon as we find a match. Instead, we continue to search until lo == hi and they contain some index at which target can be found.
The other change is the introduction of the left parameter, which is a boolean indicating what to do in the event that target == nums[mid]; if left is true, then we “recurse” on the left subarray on ties. Otherwise, we go right. To see why this is correct, consider the situation where we find target at index i. The leftmost target cannot occur at any index greater than i, so we never need to consider the right subarray. The same argument applies to the rightmost index.