4

Given a unimodal array A 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), an integer p (that is the length of the increasing first part) and k (the k-th minimum element) Give an algorithm to compute the value of the kth minimal element that 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)
KienMe
  • 41
  • 4
  • 8
    With the first part increasing and the rest decreasing, you basically have two sorted arrays. Check out [this](http://stackoverflow.com/a/12555973/1011995) or [this](http://stackoverflow.com/questions/4607945/how-to-find-the-kth-smallest-element-in-the-union-of-two-sorted-arrays) or a lot of other questions here. – Daniel Fischer Mar 25 '13 at 22:00

1 Answers1

0

For starters have another look at your indexes. You begin with:

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

But surely if arr1 is in ascending order, and arr2 is in descending order the kth minimal element will not be found in the same location.

  • Good point, this part of the code "arr1[len(arr1)-k-1]" must be arr1[k] – KienMe Mar 27 '13 at 18:50
  • If your indexes begin at 1, then you need to look at the index in this line as well: return arr2[len(arr2)-k-1] –  Mar 28 '13 at 13:17