What if we want the index of all the occurences of 40?

#1

Here, presence is declared as present or absent and frequency can also be declared but what if we want to print the indexes?

#2

@subham221
In that case since input array is sorted, you can do binary search on lower_bound
then you can traverse till element == value

If your doubt is resolved please close it

#3

Can you please elaborate it more?

#4

@subham221
Let A = [1,2,3,3,4,4,4,4,9,10]
If you need to print indexes of 4
First run binary search
You’ll get lower bound as 4
From index 4 print index till val at current index is 4, simple linear traversal

If your doubt is resolved please close it

#5

simply find the range lower bound - upper bound
it will give u all the indices
since it is sorted
conside 1 2 4 4 4 5
lower bound gives the first 4 and
upper bound gives 5
so print from lower bound to upper bound-1 that will give u all the indices of 4

#6

@seemantanishth
There is no need for upper_bound after lower_bound
It’ll be waste of logn time
Just a suggestion

#7

I created this code for finding the lower bound index, upper bound index and index of the element 40: auto lb=lower_bound(a, a+n, key); int lbI=lb-a; cout<<"lower bound index is: "<<lbI<<endl; auto ub=upper_bound(a, a+n, key); int upI=ub-a; cout<<"upper bound index is: "<<upI<<endl; cout<<"indexes of element is: "<<endl; for(int i=lbI;i<upI;i++) { cout<<i<<endl; }

#8

is this code of finding index okay?

#9

@Aarnav-Jindal-1059677350830863
consider the array
1 1 1 1 1 1 1 1 1 1 1
ur method takes O(N) time finding the upper bound will still take logn time

#10

@subham221
yes that code will work fine
if your doubt is resolved please mark it resolved

#11

@seemantanishth
You need to print all indices
So it’ll anyway take o(n) time
Your upper_bound will just a find value which is not required

#12

when considering complexities, the time taken to input and output the final result is generally not taken into account
the time for processing or reaching the result is what matters

#13

if input and output time would have been considered
nothing would be less than O(N)

#14

@seemantanishth
You should still not recommend something which will increase the time taken and is a useless operation that is all

#15

@Aarnav-Jindal-1059677350830863 you should not tell the correct method as useless when it does not take any extra complexity and is clearly the more efficient method.
Thank You.

#16

@seemantanishth
How is it more efficient when you’re running an extra function with no added benefit ?

#17

As mentioned above, my method works in 0(logn) while your works in O(n)
How is that not clear? Time taken to print a solution is not considered in complexities.

#18

@seemantanishth
In that case my solution works in one function call while yours takes 2 function calls
Clearly yours is not good
I don’t know why you can’t understand that

#19

I can’t believe I have to explain this so many times, it does not matter how many function calls you make as long as if takes lesser time.

#20

It includes covering all cases no exceptions