Algorithm : Suppose that in addition to being sorted, the entries of A are distinct integers. Design an efficient algorithm for finding an index i such that A[i] = i or indicating that no such index exist

public class SearchForIndexEqualToDataBinarySearch {

public static void main (String [] args)

{

/**

• Problem : SEARCH A SORTED ARRAY FOR A[i] = i. All integers are distinct

*

• Solutin : Do a binary search, if A[mid] > mid the no element on right of mid can fulfil this criteria.

• If A[mid] < mid then the element to be search is on right side of mid in the array.

*/

int [] input = {-5,-3,2,3,5,10,12,14,16};

findTheIndexWithDataEqualToIndex(input);

}

private static void findTheIndexWithDataEqualToIndex(int[] input) {

int low = 0;

int high = input.length – 1;

int mid = 0;

while (low <= high)

{

mid = low + (high – low)/2;

if(input[mid] == (mid + 1))

{

System.out.println(“The index and value is : “+ input[mid]);

break;

}

else if(input[mid] > (mid + 1))

{

high = mid – 1;

}

else

{

low = mid + 1;

}

}

}

}