StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Find Min and Max of the list containing N items through linear search and name them as HighValue and LowValue Let MedianIndex = (N+1)/2</p> <p>1st Order Binary Search:</p> <p>Repeat the following 4 steps until LowValue < HighValue.</p> <ol> <li><p>Get MedianValue approximately = ( HighValue + LowValue ) / 2</p></li> <li><p>Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K</p></li> <li><p>is K = MedianIndex, then return MedianValue</p></li> <li><p>is K > MedianIndex ? then HighValue = MedianValue Else LowValue = MedianValue</p></li> </ol> <p>It will be faster without consuming memory </p> <p>2nd Order Binary Search:</p> <p>LowIndex=1 HighIndex=N</p> <p>Repeat Following 5 Steps until (LowIndex < HighIndex)</p> <ol> <li><p>Get Approximate DistrbutionPerUnit=(HighValue-LowValue)/(HighIndex-LowIndex)</p></li> <li><p>Get Approximate MedianValue = LowValue + (MedianIndex-LowIndex) * DistributionPerUnit</p></li> <li><p>Get NumberOfItemsWhichAreLessThanorEqualToMedianValue = K</p></li> <li><p>is (K=MedianIndex) ? return MedianValue</p></li> <li><p>is (K > MedianIndex) ? then HighIndex=K and HighValue=MedianValue Else LowIndex=K and LowValue=MedianValue</p></li> </ol> <p>It will be faster than 1st order without consuming memory </p> <p>We can also think of fitting HighValue, LowValue and MedianValue with HighIndex, LowIndex and MedianIndex to a Parabola, and can get ThirdOrder Binary Search which will be faster than 2nd order without consuming memory and so on...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload