-2

what is time complexity of this code?

I have tried solving this using binary search but it cannot be solved in that way please help to find the complexity of this code. 


#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];

    for(int i=0;i<n;i++)
    cin>>a[i];
        int x;
    cin>>x;
    int p=-1;
    int q=n;
    while(p+1<q)
    {
        int m=(p+q)/2;
        if(a[m]<x)
        p=m;
        else
        q=m;
    }
    cout<<"j";
}
Rahul Singh Chandrabhan
  • 2,531
  • 5
  • 22
  • 33
ARCHANA YADAV
  • 15
  • 3
  • 3
    "`#include using namespace std;`" <-- two bad habits you should get rid of. – Jesper Juhl Jun 09 '19 at 16:18
  • 1
    To expand on @JesperJuhl’s comment: [Avoid `using namespace std`](https://stackoverflow.com/questions/1452721). [Avoid `#include `](https://stackoverflow.com/questions/31816095). – Tom Zych Jun 09 '19 at 17:02
  • 1
    BTW, online judges and code competitions do not teach good coding habits. Industry software engineers will reject this code in a code inspection and make you rewrite it. Rarely, do shops require this kind of code (if they do, they have horrible project managers and poor project scheduling techniques). – Thomas Matthews Jun 09 '19 at 17:27
  • Re-Tagged the question – Rahul Singh Chandrabhan Jun 10 '19 at 05:52

1 Answers1

0

Change your code to

p=m+1;
else
q=m-1;

Also terminate when you have found the element. The complexity is that of binary search, log(n).

Mr.L
  • 129
  • 10