**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

- 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]`

- 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`

.

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