Q:
You are a given a unimodal array of n distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element that runs in O(log n) time.
Ans. Divide and Conquer
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
}
WikiSree 