Wednesday, October 17, 2012

Median of Medians to find Kth Smallest

Given an array of unsorted integers find the Kth smallest element using "Median of Medians".
This method is guaranteed to work in max linear time

Solution

2 comments:

  1. you forgot to find the MOM element by recursivly calling the select at line 58. You are simply getting hte middle of medians instead of median of medians

    ReplyDelete
  2. "v = (x.length%2 == 0)? x[x.length%2-1]: x[x.length/2];"
    will always produce an error when the boolean part evaluates to true. Are you sure you didn't mean
    "v = (x.length%2 == 0)? x[x.length/2-1]: x[x.length/2];"?

    ReplyDelete

UA-36403895-1