CareerCup

IF array is sorted in increasing order
complexity - O(n)
In worst case all the elements might be equal to index value.
In this case we have to check for all i=(0 to n-1)

If array is sorted in decreasing order
complexity - O(logn)
Indexes are in increasing order and values are in decreasing order.
So, they can meet only at a single point. we can find this in O(logn)
using binary search

this can be solved like this

1>crate another array Y=a[i]-i

problem now becomes finding aal occurences of 0 in Y

2>apply BinarySearch twice
a>one for finding first index of 0
b>second for finding last index of 0

3>print all elements from a[first] to a[last]

works for unique .. increasingly sorted number array

if there is another condition that all of elements are integer?

perform a customized binary search since the array is sorted and logn solution is needed.
Hit the Middle of the Array and check if the Value of element is Greater than Index ? if so all elements to the right of it would follow the same trend so we can check at the elements to the left of it. If the value of the element is less than Index then check the right Half. If its equal to index, then check the element to the left and the right of it and so forth.
This gets a little tricky if the array has duplicate elements. In addition we may have to find whats the next unique and preceding unique element in the array.

the array should have all the element unique, otherwise log(n) not possible.Try to apply pigeonhole principle when deciding left/right side in binary search.

the array should have all the element unique, otherwise log(n) not possible.Try to apply pigeonhole principle when deciding left/right side in binary search.

public void printElement(int[] a)
{
   while(i<a.length)
   {
       if(a[i]==i)
          System.out.println(i);
       else if(a[i]>i)
         i=a[i];  //we can skip if a[i] >i
        else 
          i++;
   }
}

What if there are negative values. There is nothing given about the array containing only numbers from 1.

int func(int *A, int begin, int end)
{
    if(begin>=end) return NOT_FOUND;
    int ptr = (end-begin)/2;
    if(A[ptr]==ptr) return ptr;
    if(A[ptr]>ptr) return func(A,begin,ptr);
    if(A[ptr]<ptr) return func(A,ptr,end);
}

Simple modification to the binary search :)
O(log n)

Assumptions:
1) all positive integers.
2) no duplicates
3) input array sorted in increasing order
This means any elem in array is either greater than the index or is equal to index.

/* returns the index till which all elems in array are equal to index of array */
int search(int a[], int n)
{
   int lower = 0, upper = n-1;
   int mid;
   while(lower < upper) {
      mid = (lower+upper)/2;
      if (a[mid] == mid) {
         //good so far, search in right half.
         lower = mid+1;
      } else {
         upper = mid-1;
      }
   }
   if (a[lower] == lower)
     return lower;
   else 
     return (lower-1);
}

I think O(logn) soln is possible only when the elements r positive and distinct.......

this can be solved like this

1>crate another array Y=a[i]-i

problem now becomes finding aal occurences of 0 in Y

2>apply BinarySearch twice
a>one for finding first index of 0
b>second for finding last index of 0

3>print all elements from a[first] to a[last]

works for unique .. increasingly sorted number array

One of the best solutions to the above problem is to use the binary search in the array we will check for each of the array elements in the sorted array and we will check if the index at which the element is present must be equal to the array element of the sorted array (sorted in increasing order)