Thursday, October 11, 2012

Search in Array for A[i] == i

Problem: We have a sorted array of distinct elements, A. Find the occurrences of elements where A[i] == i.

Discussion: It pretty much the same problem as binary search once you realize how to divide. We know
  1. The array is distinct and sorted so, for each j, A.length >= j > i we will have A[j] > A[i]; and similarly, for each j, 1 <= j < i we will have A[j] < A[i]
  2. If we found out A[i] > i, so for all j > i we will have A[j] > j (from previous point). So no point in searching in right in this case.

    Similarly, if A[i] < i, no gain in searching  in left of i.
So, here is the algorithm
searchForAiI (A, low, high)
  if low > high
      return -1
      
  mid = low + (high - low)/2
  if A[mid] == mid
    return mid
  else if mid > A[mid] 
    //all the elements in right is greater than their index, so search left
    return searchForAiI (A, low, mid-1)
 else
     //all the elements in left is smaller than their index, so search right
    return searchForAiI (A, mid+1, high)     

Footnotes:
[1] View/download Java code from GitHub and get sample run here.

No comments:

Post a Comment