**Problem:**Given a sorted array of distinct integers, find index i where arr[i] = i. Note that integers in array can be negative.

**Solution:**Use binary search to get the index.

**Implementation:**

int findIndex(int arr[], int low, int high)

{

if(low <= high)

{

int mid = (low + high) / 2;

if(mid == arr[mid])

return mid;

if(mid < arr[mid])

return findIndex(arr, low, mid - 1);

else

return findIndex(arr, mid + 1, high);

}

else

return - 1;

}

**Complexity:**O(log n)

## No comments:

## Post a Comment