Q:

You are given a sorted (from smallest to largest) array A of n distinct integers which can be positive, negative, or zero. You want to decide whether or not there is an index i such that A[i] = i. Design the fastest algorithm that you can for solving this problem.

Ans.

Input: Array a[0..n-1] of n elements

pseudocode:

func(a, i, k) {

j = (i + k)/2

if (a[j]==j) return True

else if (a[j]<j) =”” return=”” <span=”” class=”hiddenSpellError” pre=”return ” data-mce-bogus=”1″>func(a, j, k) // since all numbers are distinct, a[x]

else return func(a, i, j) // since all numbers are distinct, a[x]>x for all x > j

}