Vector in c++ (auto it)

1

My code is failing 3 test cases for very large inputs(time limit) …I think the problem is with auto it operator…

#include <bits/stdc++.h> 
int main() 
{
long long int n,k;
cin>>n;
vector<int >v;
while(n--)
{
  cin>>k;
  v.push_back(k);
}
sort(v.begin(),v.end());
long long int query,x;
cin>>query;
while(query--)
{
  cin>>x;  
  auto it = find(v.begin(),v.end(),x); 
  if(it!=v.end())
  {
    cout<<"Yes "<<it-v.begin()+1<<endl;
  }

  else
  {
    auto it1=lower_bound(v.begin(),v.end(),x);
    cout<<"No "<<it1-v.begin()+1<<endl;
  }
}
 return 0;
}
1 Like
2

https://hackerrank-challenge-pdfs.s3.amazonaws.com/9403-cpp-lower-bound-English?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1582617861&Signature=xpwZorxLAoSNgtvnlvUU1cJNnu8%3D&response-content-disposition=inline%3B%20filename%3Dcpp-lower-bound-English.pdf&response-content-type=application%2Fpdf

problem link

3

Please format your code - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

while(query--)
{
cin>>x;
auto it = find(v.begin(),v.end(),x);

This loop is executed O(Q) times and std::find is linear-time, so each call takes O(N), so this is an O(N \times Q) algorithm - too slow to run in ~2 secs with N=10^5 and Q=10^5.

2 Likes
5

Ok,What if I use binary search? how will I get the index???
it=binary_search(A.begin(),A.end(),x);

6

The same way as you are doing it now:

    cout<<"Yes "<<it-v.begin()+1<<endl;

PS - the Problem states that the list is already in sorted order, so no need to sort it :slight_smile:

2 Likes
7

thank you so much:grinning::grinning:

1 Like
8

But binary_search returns 1,0; How can i store element index ??
if(binary_search(arr.begin(), arr.end(), 15))

9

Oh, sorry - I misread. Don’t use binary_search - use lower_bound like the Problem asks you to :slight_smile:

1 Like
10

I have already used lower bound in 2nd part ,What about first part which is exceeding time limit

For each query you have to print “Yes” (without the quotes) if the number is present and at which index(1-based) it is present separated by a space.

11

Just use lower_bound - there’s no real need for a “first part” and a “second part” :slight_smile:

2 Likes
12

Thank you I understood ,i missed it

1 Like
13

This is one of the weirdest in built function I feel.
I mean I end up using my own binary search function everytime because I have certain requirements and I don’t use standard binary search everytime.
I know in-built functions are useful to save a lot of time so I wanted to know if there’s a way to like modify the function to our need?
Btw to use the array value

int x=a[lower_bound(a.begin(),a.end(),target)-a.begin()]

Is a good way

1 Like