Find if there is any i so that array[i] equals i

Question:  Given a sorted array of distinct integers find the index such that a[i] = i

The brute force approach to solve this problem is O(n). The integers are distinct and sorted.Given i such that array[i] = i you have array[i] - i = 0.

For each j < i you have array[j] - j <= 0 and for j > i you have array[j] - j >= 0 because j vary of 1 at each step but array[j] vary of at least 1 (distinct and sorted numbers).

So on the left it's <=0 on the right it's >= 0. Using binary search approach you can easily find the correct position in O(log n)

 

public class BinarySearchApproach {

	public static int findIndex(int arr[])
	{
	    assert(arr != null);
	    assert(arr.length > 0);
	    int low = 0;
	    int high = arr.length-1;
	    while (low <= high)
	    {
	        int middle = (low + high)/2;
	        if (arr[middle] == middle)
	            return middle;
	        if (arr[middle] < middle)
	            low = middle + 1;
	        else
	            high = middle - 1;
	    }
	    return -1;
	}
	public static void main(String[] args) {
		int a[] = {-10, -9, -8, 3};
		System.out.println("Index is "+findIndex(a));
	}
}