divide_and_conquer.kth_order_statistic
======================================

.. py:module:: divide_and_conquer.kth_order_statistic

.. autoapi-nested-parse::

   Find the kth smallest element in linear time using divide and conquer.
   Recall we can do this trivially in O(nlogn) time. Sort the list and
   access kth element in constant time.

   This is a divide and conquer algorithm that can find a solution in O(n) time.

   For more information of this algorithm:
   https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/08/Small08.pdf



Functions
---------

.. autoapisummary::

   divide_and_conquer.kth_order_statistic.kth_number
   divide_and_conquer.kth_order_statistic.random_pivot


Module Contents
---------------

.. py:function:: kth_number(lst: list[int], k: int) -> int

   Return the kth smallest number in lst.
   >>> kth_number([2, 1, 3, 4, 5], 3)
   3
   >>> kth_number([2, 1, 3, 4, 5], 1)
   1
   >>> kth_number([2, 1, 3, 4, 5], 5)
   5
   >>> kth_number([3, 2, 5, 6, 7, 8], 2)
   3
   >>> kth_number([25, 21, 98, 100, 76, 22, 43, 60, 89, 87], 4)
   43


.. py:function:: random_pivot(lst)

   Choose a random pivot for the list.
   We can use a more sophisticated algorithm here, such as the median-of-medians
   algorithm.