Find the kth element in a unimodal matrix

Question

Given a unimodal array A of n different elements (which means that its entries are in ascending order up to its maximum element, after which its elements are in descending order), the integer p (i.e. the length of the increasing first part) and k (k- min element). Give an algorithm for calculating the value of the kth minimal element, which runs in O (log n) time.

Example:

A= {1,23,50,30,20,2} p= 2 k=3 

Answer: 20

Edit

I tried this:

 def ksmallest(arr1, arr2, k): if len(arr1) == 0: return arr2[len(arr2)-k-1] elif len(arr2) == 0: return arr1[k] mida1 = (int)(len(arr1)/2) mida2 = (int)((len(arr2)-1)/2) if mida1+mida2<k: if arr1[mida1]>arr2[mida2]: return ksmallest(arr1, arr2[:mida2], k-(len(arr2)-mida2)) else: return ksmallest(arr1[mida1+1:], arr2, k-mida1-1) else: if arr1[mida1]>arr2[mida2]: return ksmallest(arr1[:mida1], arr2, k) else: return ksmallest(arr1, arr2[mida2+1:], k) 

Answer 1

First, pay attention to your indexes. You start with:

 if len(arr1) == 0: return arr2[len(arr2)-k-1] elif len(arr2) == 0: return arr1[len(arr1)-k-1] 

But, of course, if arr1 is in increasing order, and arr2 is in decreasing order, then the k-th minimal element will not be found in the same place.