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));

}

}

## No comments:

Post a Comment