Algorithm Puzzles


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.


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


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