Skip to content

Instantly share code, notes, and snippets.

@monadplus

monadplus/randomized_median.md

Last active October 13, 2021 10:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save monadplus/a4264037dfeeb6624f0d12e5f3eebc57 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save monadplus/a4264037dfeeb6624f0d12e5f3eebc57 to your computer and use it in GitHub Desktop.
Download ZIP
Latex on markdown
Raw
randomized_median.md

Randomized Median Algorithm

Input: A set S of n elements over a totally ordered universe.

Output: The median element of S, denoted by m.

  1. Pick a (multi-)set R of elements in S, chosen independently and uniformly at random with replacement.
  2. Sort the set R.
  3. Let d be the ()th smallest element in the sorted set R.
  4. Let u be the ()th smallest element in the sorted set R.
  5. By comparing every element in S to d and u< compute the set and the numbers and .
  6. If then FAIL.
  7. If then sort the set C, otherwise FAIL.
  8. Output the ()th element in the sorted order of C.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment