学过分而治之算法的人进来看看Considerthefollowingproblem.GivenanarrayAconsistingofndistinctintegersA[0],…A[n-1].Itisknownthatthereisapositionpbetween1andn,suchthatA[0]A[n-1].1.Designadivide-and-conqueralg

Question

学过分而治之算法的人进来看看
Consider the following problem.
Given an array A consisting of n distinct integers A[0],… A[n-1].It is known that there is a position p between 1 and n,such that A[0] A[n-1] .
1.Design adivide-and-conquer algorithmto find the position p with running time of O(log n) in the worst case
2.Justify the running time of your algorithm by
i.Finding the recurrence relation for its time complexity and explain it.
ii.Solving the recurrence relation to show that the complexity of your algorithm is O(log n) (for simplicity,you can assume that n = 2k).

Answer 1

分治只是表现嘛,本质是递归recursion才对.
代码如下：
查找位置p(数组A){
v = A[A.length/2]
如果v比左侧小,查找位置p(左侧)
如果v比右侧小,查找位置p(右侧)
否则返回v
}