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

Comments

  1. the example include 4,4 which does not satisfied the n+1 or n-1

    ReplyDelete
  2. main()
    {
    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...

    ReplyDelete
  3. Algorithm :-
    Let 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

    }

    ReplyDelete

Post a Comment

Popular posts from this blog