# Searching in O(logN) in Unsorted array???

Help me find the error in analysis of the following algorithm that I came up with to search an element in a unsorted arrar in O(logN)

#include<bits/stdc++.h>
using namespace std;

int count(int *a,int st,int end,int element)// return the index of the eleme
{

if(end==st)

``````{
if(a[end]==element)
{
return end;
}
else
{
return -1;
}
}
int mid=(st+end)/2;
int j=count(a,st,mid,element);
if(j!=-1)
{
return j;
}
int k=count(a,mid+1,end,element);
if(k!=-1)
{
return k;
}
return -1;
``````

}

int main()
{

int size;

cin>>size;

int a[size];

int i=0;

while(i<size)

``````{
``````

cin>>a[i];

++i;

}

int index=count(a,0,size-1,size);

cout<<index<<endl;

return 0;

}

Isnt it basically binary search on an unsorted array?

It should take O(N) time in worst case I believe.

What is the error? I compiled the code and it worked perfectly.

For O(log N) you need some kind of order in an array, else it is impossible.

And even more important. This code is not O(\log n). It is O(n).

I was thinking to use map while storing array? Or if array elements are in some range like < 10^6 or something and you have to tell first occurring index then you can simply make an array of size max(array) and store first index of a number in thatâ€¦ Then on query you can access them in O(1). Or If there is no limit on A_i then unordered map may be more helpful, but depend on your hashing function.

Can you explain me how you come up with O(n)mathematically

Anybody can explain mathematically how it is O(n)

can you explain me how you came up with O(N) mathematical because I am using recurrence relation t(n)=2t(n/2)+O(1) which I think is the relation for the above code

//