Find a[j]=j in O(log n) time

How can I f开发者_StackOverflow中文版ind if a sorted array has an element a[j]=j in O(log n) time?(no duplicates)

If the array is of integers and cannot contain duplicates, you can just use binary search.

E.g. let's say we have the array:

a[0] == -30
a[1] == 1
a[2] == 200
a[3] == 200
a[4] == 204
a[5] == 205
a[6] == 206
a[7] == 207

• First try a[floor(avg(0,7))] (i.e. a[3]). This equals 200. 200 is too big.
• So move to the lower half. Try a[floor(avg(0,2))] (i.e. a[1]). This equals 1. Hurray!

Your binary search will either successfully find some j for which a[j] == j, or it will fail by running out of places to look. Since a binary search is O(log n), you will know within that time complexity the value of j or that no such j exists.

Note that if multiple values of j satisfy the condition, you will just find an arbitrary one of them.

If it can contain duplicate values, or it is a floating point array, you can't. Counterexample: a[2k]=2k+1, a[2k+1]=2k+1 or 2k+2. Worst case scenario, you have to check a[2k+1] for all k.

If it is an integer array and all values are distinct, then you do binary search. Look at a[1]-1 and a[n]-n. If they are the same sign, the answer is no. If they have different signs, look at a[n/2]-n/2. It's either zero (and then you have your answer), or one of the intervals (1,n/2) or (n/2,n) will have different signs at the ends. Take that interval and repeat.

Assuming duplicates are disallowed:

#include <stdio.h>

int
find_elt_idx_match( int *a, int lo, int hi )
{
  int elt, idx;
  while ( lo <= hi )
    {
      idx = lo + ( hi - lo ) / 2; /* Thanks, @andand */
      elt = a[ idx ];
      if ( elt == idx )
        {
          return 1;
        }
      if ( elt < idx )
        {
          lo = idx + 1;
        }
      else
        {
          hi = idx - 1;
        }
    }
  return 0;
}

int
main( void )
{
  int a[ 100 ];
  /* fill a */
  /* ... */
  printf( "idx:elt match? %c\n", find_elt_idx_match( a, 0, 99 ) ? 'y' : 'n' );
  return 0;
}

public int getFirstMatchedIndex(int[] oArry)
        {            
            int i = 0;
            while(i < oArry.Length )
            {
                if (oArry[i] == i)
                    return i;
                else if (oArry [i] > i)
                    i=oArry [i];
                else
                    i++;

            }
            return -1;
        }

If duplicates are not allowed, and your list is sorted according to obvious order a[i] < a[i+1] (strictly less, not equal!), then it is also true that a[i]-i < a[i+1] - i, so it follows that a[i]-i <= a[i] - (i+1). (Note the inequality becomes "<=".) In other words, the values of a[i]-i, throughout your list, are in order. Search for the value 0=a[i]-i, using binary search on a sorted list.