### [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

}