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

help
, ,
1

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;

}

2

Isnt it basically binary search on an unsorted array?

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

3

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

4

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

5

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

6

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.

7

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

8

Anybody can explain mathematically how it is O(n)

9

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