[Adobe]Search for an element in unsorted array
The successive elements of an unsorted array differ by either + 1 or -1. How will u search for an integer k in this array ?
eg: 4,5,4,4,5,6,7,8,7
for each element 'n' the next element is always n+1 or n-1.
eg: 4,5,4,4,5,6,7,8,7
for each element 'n' the next element is always n+1 or n-1.
the example include 4,4 which does not satisfied the n+1 or n-1
ReplyDeleteyeah you can another example..:)
Delete-ve no.'s included??
ReplyDeletemain()
ReplyDelete{
int a[50];
int i=0,d,t,n;
printf("enter no.of numbers");
scanf("%d",&n);
for(i=0;it)
d=a[i]-t;
else
d=t-a[i];
}
i=i+d;
}
}
hope this works...
Algorithm :-
ReplyDeleteLet the size of array ARR be N, and element to search be K.
low = 0, up = N-1;
while( low<=up ){
offset = abs(K-a[low]);
if K does not lie in the range { a[low]-up, a[low]+up } , return false
temp = ARR[low+offset];
if( temp == K ) , return the index(low+offset) ;
else low = offset;
Time Complexity :- Worst case can be O(N)
Average case can be O(N/K), because every time we are moving K elements forward
}