We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Find the Median
  5. Discussions

Find the Median

Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • cjerian
    7 years ago+ 0 comments

    The way I did this is to notice that we are certain of only the location of the pivot, if we have l items less than the pivot, then the pivot is in the lth position, if the we count from 0. The median is the object at the len(ar)//2 position starting at 0 for odd number arrays. So we try to find that position.
    If the position we are looking for is in the left partition we just recurse for the same position on the left side (pos < len(leftside)) If the position is in the right side we recurse on that side to search for position pos- len(leftside) -1 Since the positions in the right side start after the leftside positions + 1 for the pivot. Eventually you will get an array of size one and a search for position 0, which only has a pivot and no right or left side, and you have found the answer. This method should find any kth order statistic, such as the 0th or minimum and the len(ar)-1 th or maximum

    9|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature